Submission #10376407


Source Code Expand

//Link : https://atcoder.jp/contests/agc002/tasks/agc002_d

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100001

int a[N],b[N];
int dsu[N],sz[N];

int f(int x) {
  if(dsu[x]==x) {
    return x;
  }
  return dsu[x] = f(dsu[x]);
}

void merge(int x,int y) {
  x = f(x), y= f(y);
  if(x==y) {
    return;
  } else {
    dsu[x] = y;
    sz[y] += sz[x];
  }
}

int l[N],r[N],x[N],y[N],z[N];
vector<int> query[N];
void solve() {
  int n,m;
  scanf("%d %d", &n,&m);
  for(int i=1;i<=m;++i) {
    scanf("%d %d ", &a[i],&b[i]);
  }
  int q;
  scanf("%d ", &q);
  for(int i=0;i<q;++i) {
    scanf("%d %d %d ", &x[i],&y[i],&z[i]);
    l[i] = 1,r[i] = m;
  }
  while(true) {
    bool isEnd = true;
    for(int i=0;i<q;++i) {
      if(l[i]==r[i]) {
        continue;
      }
      isEnd = false;
      int mid = (l[i]+r[i])/2;
      query[mid].push_back(i);
    }
    if(isEnd) {
      break;
    }
    for(int i=n;i;--i) {
      dsu[i] = i;
      sz[i] = 1;
    }
    for(int i=1;i<=m;++i) {
      merge(a[i],b[i]);
      while(query[i].size()>0) {
        int id = query[i].back();
        query[i].pop_back();
        int u = f(x[id]), v= f(y[id]), num = 0;
        if(u==v) {
          num += sz[u];
        } else {
          num = sz[u] + sz[v];
        }
        if(num>= z[id]) {
          r[id] = i;
        } else {
          l[id] = i+1;
        }
      }
    }
  }
  for(int i=0;i<q;++i) {
    printf("%d\n", l[i]);
  }
}

int main() {
    //freopen("input.txt","r",stdin);
    solve();
    return 0;
}

Submission Info

Submission Time
Task D - Stamp Rally
User ffresh
Language C++14 (GCC 5.4.1)
Score 1000
Code Size 1621 Byte
Status AC
Exec Time 215 ms
Memory 17400 KB

Compile Error

./Main.cpp: In function ‘void solve()’:
./Main.cpp:32:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &n,&m);
                        ^
./Main.cpp:34:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d ", &a[i],&b[i]);
                                 ^
./Main.cpp:37:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d ", &q);
                   ^
./Main.cpp:39:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d %d ", &x[i],&y[i],&z[i]);
                                          ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1000 / 1000
Status
AC × 1
AC × 33
Set Name Test Cases
Sample 0_00.txt
All 0_00.txt, 1_00.txt, 1_01.txt, 1_02.txt, 1_03.txt, 1_04.txt, 1_05.txt, 1_06.txt, 1_07.txt, 1_08.txt, 1_09.txt, 1_10.txt, 1_11.txt, 1_12.txt, 1_13.txt, 1_14.txt, 1_15.txt, 1_16.txt, 1_17.txt, 1_18.txt, 1_19.txt, 1_20.txt, 1_21.txt, 1_22.txt, 1_23.txt, 1_24.txt, 1_25.txt, 1_26.txt, 1_27.txt, 1_28.txt, 1_29.txt, 1_30.txt, 1_31.txt
Case Name Status Exec Time Memory
0_00.txt AC 3 ms 4352 KB
1_00.txt AC 136 ms 17400 KB
1_01.txt AC 178 ms 17144 KB
1_02.txt AC 140 ms 17016 KB
1_03.txt AC 175 ms 16504 KB
1_04.txt AC 141 ms 16888 KB
1_05.txt AC 183 ms 16888 KB
1_06.txt AC 150 ms 16760 KB
1_07.txt AC 188 ms 16888 KB
1_08.txt AC 148 ms 16632 KB
1_09.txt AC 194 ms 16888 KB
1_10.txt AC 160 ms 16632 KB
1_11.txt AC 196 ms 16888 KB
1_12.txt AC 172 ms 16376 KB
1_13.txt AC 186 ms 17016 KB
1_14.txt AC 141 ms 15736 KB
1_15.txt AC 139 ms 15736 KB
1_16.txt AC 178 ms 14340 KB
1_17.txt AC 206 ms 15356 KB
1_18.txt AC 204 ms 15356 KB
1_19.txt AC 180 ms 14892 KB
1_20.txt AC 194 ms 15228 KB
1_21.txt AC 188 ms 14844 KB
1_22.txt AC 202 ms 15228 KB
1_23.txt AC 207 ms 15496 KB
1_24.txt AC 215 ms 15864 KB
1_25.txt AC 198 ms 15352 KB
1_26.txt AC 192 ms 14904 KB
1_27.txt AC 199 ms 15224 KB
1_28.txt AC 191 ms 15000 KB
1_29.txt AC 215 ms 15480 KB
1_30.txt AC 202 ms 15356 KB
1_31.txt AC 193 ms 15096 KB