oj.uz

Submission #25775

# Submission time Handle Problem Language Result Execution time Memory
25775 2017-06-24T06:02:40 Z 김현수(#1080) 전압 (JOI14_voltage) C++11
100 / 100
 579 ms 32928 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, 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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 23256 KB Output is correct
2 Correct 0 ms 23256 KB Output is correct
3 Correct 0 ms 23256 KB Output is correct
4 Correct 3 ms 23116 KB Output is correct
5 Correct 0 ms 23248 KB Output is correct
6 Correct 0 ms 23248 KB Output is correct
7 Correct 3 ms 23248 KB Output is correct
8 Correct 0 ms 23248 KB Output is correct
9 Correct 0 ms 23264 KB Output is correct
10 Correct 3 ms 23252 KB Output is correct
11 Correct 0 ms 23252 KB Output is correct
12 Correct 0 ms 23252 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 27348 KB Output is correct
2 Correct 83 ms 28868 KB Output is correct
3 Correct 56 ms 27348 KB Output is correct
4 Correct 136 ms 29832 KB Output is correct
5 Correct 3 ms 23528 KB Output is correct
6 Correct 119 ms 28060 KB Output is correct
7 Correct 166 ms 28860 KB Output is correct
8 Correct 169 ms 30564 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 27348 KB Output is correct
2 Correct 53 ms 30844 KB Output is correct
3 Correct 46 ms 30848 KB Output is correct
4 Correct 0 ms 23116 KB Output is correct
5 Correct 116 ms 26956 KB Output is correct
6 Correct 126 ms 26812 KB Output is correct
7 Correct 163 ms 28660 KB Output is correct
8 Correct 149 ms 26904 KB Output is correct
9 Correct 133 ms 29024 KB Output is correct
10 Correct 149 ms 26868 KB Output is correct
11 Correct 96 ms 26812 KB Output is correct
12 Correct 146 ms 26680 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 31236 KB Output is correct
2 Correct 83 ms 32928 KB Output is correct
3 Correct 0 ms 23116 KB Output is correct
4 Correct 169 ms 28020 KB Output is correct
5 Correct 199 ms 29580 KB Output is correct
6 Correct 179 ms 27736 KB Output is correct
7 Correct 393 ms 29724 KB Output is correct
8 Correct 329 ms 29668 KB Output is correct
9 Correct 453 ms 29800 KB Output is correct
10 Correct 433 ms 29760 KB Output is correct
11 Correct 409 ms 29700 KB Output is correct
12 Correct 456 ms 29808 KB Output is correct
13 Correct 166 ms 29364 KB Output is correct
14 Correct 353 ms 30188 KB Output is correct
15 Correct 523 ms 29788 KB Output is correct
16 Correct 406 ms 29516 KB Output is correct
17 Correct 579 ms 31648 KB Output is correct
18 Correct 199 ms 31612 KB Output is correct