Submission #42714252

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)(n);i++)
ll read(){ll r;scanf("%lld",&r);return r;}
int const N=200000;
int a[N+10];
int b[N+10];
int f[N+10];
array<int,2> ev[N+10]; // edge vertex
int ans[N];
vector<int>e[N+10];
int find(int x){ return x==f[x]?x:find(f[x]); } // 不做路径压缩
void dfs(int x,int fa,int s){
  int fx=find(a[x]);
  int fy=find(b[x]);
  if(ev[fx][1] > ev[fy][1]) swap(fx,fy);
  auto [ex,vx] = ev[fx];
  auto [ey,vy] = ev[fy];
  if(fx != fy){
    f[fx] = fy;
    ev[fy] = {ex+ey+1,max(1,vx)+max(1,vy)};
    ans[x] = (s+= min(ev[fy][0],ev[fy][1]) - (min(ex,vx) + min(ey,vy)));
  }else{
    ev[fy] = {ey+1,max(1,vy)};
    ans[x] = (s+= min(ev[fy][0],ev[fy][1]) - min(ey,vy));
  }
  for(int y:e[x]) if(y!=fa) dfs(y,x,s);
  f[fx] = fx;
  ev[fy] = {ey,vy};
}
int main(){
  int n=read();
  rep(i,1,n+1){
    a[i]=read();
    b[i]=read();
    f[i]=i;
  }
  rep(i,1,n) {
    int x=read();
    int y=read();
    e[x].push_back(y);
    e[y].push_back(x);
  }
  dfs(1,0,0);
  rep(i,2,n+1) printf("%d ",ans[i]);
  return 0;
}

Submission Info

Submission Time
Task Ex - Ball Collector
User cromarmot
Language C++ (GCC 9.2.1)
Score 625
Code Size 1106 Byte
Status AC
Exec Time 203 ms
Memory 38116 KiB

Compile Error

./Main.cpp: In function ‘ll read()’:
./Main.cpp:5:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    5 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 625 / 625
Status
AC × 2
AC × 62
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, test_00.txt, test_01.txt, test_02.txt, test_03.txt, test_04.txt, test_05.txt, test_06.txt, test_07.txt, test_08.txt, test_09.txt, test_10.txt, test_11.txt, test_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt, test_29.txt, test_30.txt, test_31.txt, test_32.txt, test_33.txt, test_34.txt, test_35.txt, test_36.txt, test_37.txt, test_38.txt, test_39.txt, test_40.txt, test_41.txt, test_42.txt, test_43.txt, test_44.txt, test_45.txt, test_46.txt, test_47.txt, test_48.txt, test_49.txt, test_50.txt, test_51.txt, test_52.txt, test_53.txt, test_54.txt, test_55.txt, test_56.txt, test_57.txt, test_58.txt, test_59.txt
Case Name Status Exec Time Memory
example_00.txt AC 11 ms 8260 KiB
example_01.txt AC 8 ms 8400 KiB
test_00.txt AC 153 ms 18992 KiB
test_01.txt AC 77 ms 13892 KiB
test_02.txt AC 79 ms 13456 KiB
test_03.txt AC 85 ms 14424 KiB
test_04.txt AC 67 ms 12780 KiB
test_05.txt AC 59 ms 12140 KiB
test_06.txt AC 28 ms 9472 KiB
test_07.txt AC 118 ms 15908 KiB
test_08.txt AC 20 ms 8964 KiB
test_09.txt AC 89 ms 14064 KiB
test_10.txt AC 174 ms 19492 KiB
test_11.txt AC 171 ms 19300 KiB
test_12.txt AC 188 ms 19452 KiB
test_13.txt AC 203 ms 19404 KiB
test_14.txt AC 199 ms 19560 KiB
test_15.txt AC 147 ms 37980 KiB
test_16.txt AC 140 ms 37980 KiB
test_17.txt AC 139 ms 38032 KiB
test_18.txt AC 139 ms 38116 KiB
test_19.txt AC 140 ms 37924 KiB
test_20.txt AC 114 ms 19508 KiB
test_21.txt AC 114 ms 19904 KiB
test_22.txt AC 114 ms 19512 KiB
test_23.txt AC 115 ms 19352 KiB
test_24.txt AC 113 ms 19444 KiB
test_25.txt AC 122 ms 19200 KiB
test_26.txt AC 125 ms 19304 KiB
test_27.txt AC 125 ms 19372 KiB
test_28.txt AC 126 ms 19236 KiB
test_29.txt AC 124 ms 19236 KiB
test_30.txt AC 115 ms 19588 KiB
test_31.txt AC 119 ms 19388 KiB
test_32.txt AC 117 ms 19384 KiB
test_33.txt AC 118 ms 19432 KiB
test_34.txt AC 115 ms 19408 KiB
test_35.txt AC 27 ms 10340 KiB
test_36.txt AC 22 ms 10392 KiB
test_37.txt AC 26 ms 10412 KiB
test_38.txt AC 21 ms 10492 KiB
test_39.txt AC 21 ms 10404 KiB
test_40.txt AC 153 ms 17900 KiB
test_41.txt AC 155 ms 17900 KiB
test_42.txt AC 156 ms 18008 KiB
test_43.txt AC 150 ms 17900 KiB
test_44.txt AC 150 ms 18020 KiB
test_45.txt AC 149 ms 17948 KiB
test_46.txt AC 150 ms 17972 KiB
test_47.txt AC 155 ms 17820 KiB
test_48.txt AC 152 ms 17948 KiB
test_49.txt AC 163 ms 17816 KiB
test_50.txt AC 162 ms 18012 KiB
test_51.txt AC 150 ms 17748 KiB
test_52.txt AC 145 ms 17896 KiB
test_53.txt AC 146 ms 17876 KiB
test_54.txt AC 145 ms 17816 KiB
test_55.txt AC 136 ms 17768 KiB
test_56.txt AC 143 ms 17924 KiB
test_57.txt AC 134 ms 17780 KiB
test_58.txt AC 137 ms 17892 KiB
test_59.txt AC 140 ms 17748 KiB