oj.uz

Submission #25764

# Submission time Handle Problem Language Result Execution time Memory
25764 2017-06-24T05:34:37 Z 김현수(#1080) 전압 (JOI14_voltage) C++11
0 / 100
 753 ms 41740 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;

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, V;
		scanf("%lld%lld",&A,&B);
		if(A > B) swap(A, B);
		pll X = {A, B}; V = mp[X];
		if(ds.Union(A, B)) {
			if(V == 0) mp[X] = 1;
			adj[A].push_back(B);
			adj[B].push_back(A);
		}
		else {
			if(V >= 1) {mp[X] = -1; cnt += 1-V;}
			if(V == 0) {mp[X] = 2; cnt++;}
			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);
		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++;
	if(tot == 0) ans += cnt;
	printf("%lld\n", ans);
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:67: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:71: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 23252 KB Output is correct
2 Correct 0 ms 23260 KB Output is correct
3 Correct 0 ms 23260 KB Output is correct
4 Correct 3 ms 23252 KB Output is correct
5 Incorrect 3 ms 23252 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 179 ms 33548 KB Output is correct
2 Correct 319 ms 35072 KB Output is correct
3 Correct 206 ms 33548 KB Output is correct
4 Correct 273 ms 36040 KB Output is correct
5 Correct 23 ms 24192 KB Output is correct
6 Incorrect 273 ms 34264 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 33548 KB Output is correct
2 Correct 99 ms 37052 KB Output is correct
3 Correct 106 ms 37052 KB Output is correct
4 Correct 0 ms 23120 KB Output is correct
5 Correct 206 ms 31976 KB Output is correct
6 Correct 269 ms 33152 KB Output is correct
7 Incorrect 283 ms 34868 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 37492 KB Output is correct
2 Correct 173 ms 39184 KB Output is correct
3 Correct 0 ms 23120 KB Output is correct
4 Correct 293 ms 34776 KB Output is correct
5 Correct 323 ms 36452 KB Output is correct
6 Correct 309 ms 34492 KB Output is correct
7 Incorrect 753 ms 41740 KB Output isn't correct
8 Halted 0 ms 0 KB -