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 |
|
|
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 |