Submission #25777

#	Time	Username	Problem	Language	Result	Execution time	Memory
25777		khsoo01	전압 (JOI14_voltage)	C++11	100 / 100	516 ms	32932 KiB

voltage

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll N = 100005, M = 200005, L = 20;

ll n, m, col[N], dep[N], par[L][N], cap[N], tot, ans;

vector<ll> adj[N];
vector<pll> ex;

struct disj {
	ll par[N], con;
	void init () {
		for(ll i=1;i<=n;i++) par[i] = i;
		con = 0;
	}
	ll Find (ll X) {
		if(par[X] == X) return X;
		return par[X] = Find(par[X]);
	}
	bool Union (ll A, ll B) {
		A = Find(A); B = Find(B);
		if(A == B) return false;
		par[A] = B; con++;
		return true;
	}
} ds;

ll getlca (ll A, ll B) {
	if(dep[A] < dep[B]) swap(A, B);
	for(ll i=L;i--;) {
		if(dep[A] - dep[B] >= (1<<i)) {
			A = par[i][A];
		}
	}
	if(A == B) return A;
	for(ll i=L;i--;) {
		if(par[i][A] != par[i][B]) {
			A = par[i][A]; B = par[i][B];
		}
	}
	return par[0][A];
}

void calc (ll C, ll P) {
	par[0][C] = P;
	col[C] = col[P] ^ 1;
	dep[C] = dep[P] + 1;
	for(auto &T : adj[C]) {
		if(T == P) continue;
		calc(T, C);
	}
}

void pull (ll C, ll P) {
	for(auto &T : adj[C]) {
		if(T == P) continue;
		pull(T, C);
		cap[C] += cap[T];
	}
}

int main()
{
	scanf("%lld%lld",&n,&m);
	ds.init();
	for(ll i=1;i<=m;i++) {
		ll A, B, V;
		scanf("%lld%lld",&A,&B);
		if(ds.Union(A, B)) {
			adj[A].push_back(B);
			adj[B].push_back(A);
		}
		else ex.push_back({A, B});
	}
	for(ll i=1;i<=n;i++) {
		if(!dep[i]) calc(i, 0);
	}
	for(ll k=1;k<L;k++) {
		for(ll i=1;i<=n;i++) {
			par[k][i] = par[k-1][par[k-1][i]];
		}
	}
	for(auto &T : ex) {
		ll A, B; tie(A, B) = T;
		ll V = 2*(col[A] == col[B]) - 1, C = getlca(A, B);
		if(V == 1) tot++;
		cap[A] += V; cap[B] += V; cap[C] -= 2*V;
	}
	for(ll i=1;i<=n;i++) {
		if(dep[i] == 1) pull(i, 0);
		else if(tot == cap[i]) ans++;
	}
	if(tot == 1) ans++;
	printf("%lld\n", ans);
}

Compilation message (stderr)

voltage.cpp: In function 'int main()':
voltage.cpp:69:12: warning: unused variable 'V' [-Wunused-variable]
   ll A, B, V;
            ^
voltage.cpp:66:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld",&n,&m);
                         ^
voltage.cpp:70:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&A,&B);
                          ^

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45