oj.uz

Submission #25777

# Submission time Handle Problem Language Result Execution time Memory
25777 2017-06-24T06:06:01 Z khsoo01 전압 (JOI14_voltage) C++11
100 / 100
 516 ms 32932 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 0 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 3 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 3 ms 23252 KB Output is correct
12 Correct 3 ms 23252 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 27348 KB Output is correct
2 Correct 163 ms 28868 KB Output is correct
3 Correct 63 ms 27348 KB Output is correct
4 Correct 123 ms 29836 KB Output is correct
5 Correct 6 ms 23524 KB Output is correct
6 Correct 79 ms 28052 KB Output is correct
7 Correct 96 ms 28856 KB Output is correct
8 Correct 83 ms 30556 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 27348 KB Output is correct
2 Correct 46 ms 30848 KB Output is correct
3 Correct 43 ms 30844 KB Output is correct
4 Correct 0 ms 23116 KB Output is correct
5 Correct 93 ms 26956 KB Output is correct
6 Correct 86 ms 26812 KB Output is correct
7 Correct 179 ms 28660 KB Output is correct
8 Correct 143 ms 26900 KB Output is correct
9 Correct 159 ms 29020 KB Output is correct
10 Correct 136 ms 26868 KB Output is correct
11 Correct 79 ms 26812 KB Output is correct
12 Correct 89 ms 26680 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 31236 KB Output is correct
2 Correct 86 ms 32932 KB Output is correct
3 Correct 3 ms 23116 KB Output is correct
4 Correct 173 ms 28020 KB Output is correct
5 Correct 213 ms 29580 KB Output is correct
6 Correct 196 ms 27740 KB Output is correct
7 Correct 473 ms 29724 KB Output is correct
8 Correct 393 ms 29672 KB Output is correct
9 Correct 406 ms 29800 KB Output is correct
10 Correct 449 ms 29760 KB Output is correct
11 Correct 386 ms 29700 KB Output is correct
12 Correct 469 ms 29808 KB Output is correct
13 Correct 246 ms 29364 KB Output is correct
14 Correct 516 ms 30188 KB Output is correct
15 Correct 403 ms 29788 KB Output is correct
16 Correct 299 ms 29516 KB Output is correct
17 Correct 383 ms 31648 KB Output is correct
18 Correct 116 ms 31612 KB Output is correct