oj.uz

Submission #218662

# Submission time Handle Problem Language Result Execution time Memory
218662 2020-04-02T13:19:32 Z jjaewon None (KOI17_cat) C++14
12 / 100
 2000 ms 10856 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define endl '\n'
#define y1 holyshit
const int inf=0x3f3f3f3f;

int N,M;
pii edge[300010];

int p[300010];
int find(int x){ return x==p[x]?x:p[x]=find(p[x]); }
bool merge(int x,int y){
	x=find(x); y=find(y);
	if(x==y) return false;
	return p[x]=y;
}
bool solve(int x){
	for(int i=1;i<=N;i++) p[i]=i;
	for(int i=0;i<M;i++){
		if(edge[i].fi==x||edge[i].se==x) continue;
		if(!merge(edge[i].fi,edge[i].se)) return false;
	}
	return true;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=0;i<M;i++){
    	cin>>edge[i].fi>>edge[i].se;
    	if(edge[i].fi>edge[i].se) swap(edge[i].fi,edge[i].se);
    }
    int ans=0;
    for(int i=1;i<=N;i++) if(solve(i)) ans+=i;
    cout<<ans;
    return 0;
}

Compilation message

cat.cpp: In function 'bool merge(int, int)':
cat.cpp:20:13: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  return p[x]=y;
         ~~~~^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 526 ms 632 KB Output is correct
6 Correct 1093 ms 608 KB Output is correct
7 Correct 370 ms 512 KB Output is correct
8 Correct 997 ms 520 KB Output is correct
9 Correct 340 ms 544 KB Output is correct
10 Correct 563 ms 512 KB Output is correct
11 Correct 354 ms 532 KB Output is correct
12 Correct 477 ms 512 KB Output is correct
13 Correct 624 ms 512 KB Output is correct
14 Correct 771 ms 516 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 267 ms 532 KB Output is correct
21 Correct 358 ms 516 KB Output is correct
22 Correct 355 ms 512 KB Output is correct
23 Correct 19 ms 512 KB Output is correct
24 Correct 15 ms 512 KB Output is correct
25 Correct 5 ms 384 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2075 ms 7752 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 23.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2079 ms 10856 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 526 ms 632 KB Output is correct
6 Correct 1093 ms 608 KB Output is correct
7 Correct 370 ms 512 KB Output is correct
8 Correct 997 ms 520 KB Output is correct
9 Correct 340 ms 544 KB Output is correct
10 Correct 563 ms 512 KB Output is correct
11 Correct 354 ms 532 KB Output is correct
12 Correct 477 ms 512 KB Output is correct
13 Correct 624 ms 512 KB Output is correct
14 Correct 771 ms 516 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 4 ms 384 KB Output is correct
19 Correct 5 ms 384 KB Output is correct
20 Correct 267 ms 532 KB Output is correct
21 Correct 358 ms 516 KB Output is correct
22 Correct 355 ms 512 KB Output is correct
23 Correct 19 ms 512 KB Output is correct
24 Correct 15 ms 512 KB Output is correct
25 Correct 5 ms 384 KB Output is correct
26 Execution timed out 2075 ms 7752 KB Time limit exceeded
27 Halted 0 ms 0 KB -