Submission #218662

#	Time	Username	Problem	Language	Result	Execution time	Memory
218662		jjaewon	산만한 고양이 (KOI17_cat)	C++14	12 / 100	2079 ms	10856 KiB

cat

#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 (stderr)

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 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 23
• Subtask 4: 0 / 55