Submission #283248

#	Time	Username	Problem	Language	Result	Execution time	Memory
283248		jjaewon	산만한 고양이 (KOI17_cat)	C++14	100 / 100	441 ms	70068 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,dep[300010],fu[300010],hf[300010],up[300010];
vector<int> edge[300010],ch[300010];

void dfs(int now,int prv){
	for(auto i:edge[now]) if(i!=prv){
		if(!dep[i]){
			dep[i]=dep[now]+1;
			ch[now].push_back(i);
			int t=fu[now];
			dfs(i,now);
			up[i]=fu[now]-t;
			fu[now]+=fu[i];
			hf[now]+=hf[i];
		}
		else if(dep[now]>dep[i]) fu[i]++, hf[now]++;
	}
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>M;
    for(int i=0;i<M;i++){
    	int u,v; cin>>u>>v;
    	edge[u].push_back(v);
    	edge[v].push_back(u);
    }
    dep[1]=1; dfs(1,1);
    ll ans=0;
    for(int i=1;i<=N;i++){
    	bool flag=(M-N+1-hf[i]==0);
    	for(auto j:ch[i]) flag&=(hf[j]-up[j]<2&&fu[j]<1);
    	if(flag) ans+=i;
    }
    cout<<ans;
    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 10 / 10
• Subtask 3: 23 / 23
• Subtask 4: 55 / 55