oj.uz

Submission #25756

# Submission time Handle Problem Language Result Execution time Memory
25756 2017-06-24T05:02:30 Z 김현수(#1080) 전압 (JOI14_voltage) C++11
0 / 100
 306 ms 39284 KB 
#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, cnt, col[N], dep[N], par[L][N], cap[N], tot, ans;
bool blk[N];

vector<ll> adj[N];
vector<pll> ex;
map<pll, ll> mp;

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;
		scanf("%lld%lld",&A,&B);
		if(A > B) swap(A, B);
		pll X = {A, B};
		if(mp[X] == 1) {mp[X] = -1; cnt--;}
		if(mp[X] == 0) {mp[X] = 1; cnt++;}
		if(ds.Union(A, B)) {
			adj[A].push_back(B);
			adj[B].push_back(A);
		}
		else ex.push_back(X);
	}
	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;
		if(dep[A] < dep[B]) swap(A, B);
		if(par[0][A] == B) blk[A] = true;
		if(col[A] != col[B]) continue;
		ll C = getlca(A, B); tot++;
		cap[A]++; cap[B]++; cap[C] -= 2;
	}
	if(tot == 0) {printf("%lld\n", cnt); return 0;}
	for(ll i=1;i<=n;i++) {
		if(dep[i] == 1) pull(i, 0);
		if(!blk[i] && tot == cap[i]) ans++;
	}
	printf("%lld\n", ans+(tot==1));
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:68: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:72: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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 23352 KB Output is correct
2 Correct 0 ms 23360 KB Output is correct
3 Correct 3 ms 23360 KB Output is correct
4 Correct 3 ms 23352 KB Output is correct
5 Incorrect 3 ms 23352 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 239 ms 33648 KB Output is correct
2 Correct 279 ms 35176 KB Output is correct
3 Correct 216 ms 33648 KB Output is correct
4 Correct 306 ms 36144 KB Output is correct
5 Correct 16 ms 24288 KB Output is correct
6 Incorrect 246 ms 34364 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 33648 KB Output is correct
2 Correct 116 ms 37152 KB Output is correct
3 Correct 119 ms 37156 KB Output is correct
4 Incorrect 0 ms 23220 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 37592 KB Output is correct
2 Correct 199 ms 39284 KB Output is correct
3 Correct 6 ms 23220 KB Output is correct
4 Incorrect 306 ms 34876 KB Output isn't correct
5 Halted 0 ms 0 KB -