oj.uz

Submission #129712

# Submission time Handle Problem Language Result Execution time Memory
129712 2019-07-13T05:23:49 Z 윤교준(#3140) 전압 (JOI14_voltage) C++14
100 / 100
 569 ms 34048 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
using namespace std;
typedef pair<int, int> pii;

const bool debug = 0;
const int MAXN = 100055;
const int MAXM = 200055;

vector<int> G[MAXN];
vector<pii> EV;
int prt[17][MAXN], dep[MAXN];
bitset<MAXN> chk;

int C[MAXN], D[MAXN];
int A[MAXM], B[MAXM];

vector<pii> AnsV;
int N, M, K, Ans;

int lca(int a, int b) {
	if(dep[a] > dep[b]) swap(a, b);
	const int dt = dep[b]-dep[a];
	for(int i = 17; i--;) if(dt & (1<<i))
		b = prt[i][b];
	if(a == b) return a;
	for(int i = 17; i--;) if(prt[i][a] != prt[i][b]) {
		a = prt[i][a];
		b = prt[i][b];
	}
	return prt[0][a];
}

int getDist(int a, int b) {
	int c = lca(a, b);
	return (dep[a]-dep[c]) + (dep[b]-dep[c]);
}

void dfsall(int i) {
	chk[i] = true;
	for(int v : G[i]) {
		dfsall(v);
		C[i] += C[v];
		D[i] += D[v];
	}
}

void process() {
	for(int i = 1; i <= M; i++) if(dep[A[i]] > dep[B[i]]) swap(A[i], B[i]);
	sorv(EV);

	for(int i = 1, a, b, c, l, *v; i <= M; i++) {
		a = A[i]; b = B[i];
		int ei = int(lower_bound(allv(EV), pii(a, b)) - EV.begin());
		if(ei < sz(EV) && pii(a, b) == EV[ei]) continue;
		l = getDist(a, b); c = lca(a, b);
		v = (l&1) ? D : C;
		v[c] -= 2;
		v[a]++; v[b]++;
		if(!(l&1)) { AnsV.eb(a, b); K++; }
	}
	if(debug) {
		printf("K=%d : ", K);
		for(auto &v : AnsV) printf("(%d,%d) ", v.first, v.second);
		puts("");
	}
	if(1 != K) AnsV.clear();

	chk.reset();
	for(int i = 1; i <= N; i++) if(!chk[i]) dfsall(i);
	for(int i = 1; i <= N; i++) if(!D[i] && C[i] == K)
		AnsV.eb(prt[0][i], i);
	
	if(debug) {
		for(int i = 1; i <= N; i++)
			printf("i=%d, C=%d, D=%d\n", i, C[i], D[i]);
	}
	
	{
		set<pii> PQ;
		vector<pii> V, MV;
		for(int i = 1, a, b; i <= M; i++) {
			a = A[i]; b = B[i];
			if(a > b) swap(a, b);
			auto it = PQ.find({a, b});
			if(PQ.end() != it) {
				MV.eb(a, b);
				continue;
			}
			PQ.insert({a, b});
		}
		PQ.clear();
		for(auto &v : MV) PQ.insert(v);

		for(auto &e : AnsV) {
			int a, b; tie(a, b) = e;
			if(a > b) swap(a, b);
			if(a < 1 || N < b) continue;
			auto it = PQ.find({a, b});
			if(PQ.end() != it) continue;
			V.eb(a, b);
		}

		sorv(V); univ(V);
		swap(AnsV, V);
	}
}

void dfs(int i) {
	chk[i] = true;
	for(int e : G[i]) {
		int v = A[e]^B[e]^i;
		if(chk[v]) continue;
		EV.eb(i, v);
		prt[0][v] = i;
		dep[v] = dep[i] + 1;
		dfs(v);
	}
}

void makeForest() {
	for(int i = 1; i <= N; i++) if(!chk[i]) {
		dep[i] = 1;
		dfs(i);
	}
	for(int j = 1; j < 17; j++) for(int i = 1; i <= N; i++)
		prt[j][i] = prt[j-1][prt[j-1][i]];
	for(int i = 1; i <= N; i++) G[i].clear();
	for(auto &e : EV) G[e.first].eb(e.second);

	if(debug) {
	for(auto &e : EV) printf("EDG %d %d\n", e.first, e.second);
	for(int i = 1; i <= N; i++) printf("i=%d, dep=%d, prt=%d\n", i, dep[i], prt[0][i]);
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N >> M;
	for(int i = 1; i <= M; i++) {
		cin >> A[i] >> B[i];
		G[A[i]].eb(i);
		G[B[i]].eb(i);
	}

	makeForest();
	process();

	cout << sz(AnsV) << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3064 KB Output is correct
2 Correct 5 ms 2936 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 6 ms 2936 KB Output is correct
5 Correct 7 ms 3064 KB Output is correct
6 Correct 6 ms 3064 KB Output is correct
7 Correct 7 ms 3064 KB Output is correct
8 Correct 7 ms 3064 KB Output is correct
9 Correct 5 ms 3064 KB Output is correct
10 Correct 6 ms 3064 KB Output is correct
11 Correct 6 ms 3064 KB Output is correct
12 Correct 6 ms 3064 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 21584 KB Output is correct
2 Correct 224 ms 25448 KB Output is correct
3 Correct 152 ms 20736 KB Output is correct
4 Correct 223 ms 25996 KB Output is correct
5 Correct 19 ms 5112 KB Output is correct
6 Correct 214 ms 23628 KB Output is correct
7 Correct 225 ms 28140 KB Output is correct
8 Correct 251 ms 27488 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 21140 KB Output is correct
2 Correct 121 ms 28140 KB Output is correct
3 Correct 120 ms 28132 KB Output is correct
4 Correct 4 ms 2936 KB Output is correct
5 Correct 168 ms 20984 KB Output is correct
6 Correct 203 ms 21984 KB Output is correct
7 Correct 211 ms 24548 KB Output is correct
8 Correct 236 ms 25580 KB Output is correct
9 Correct 210 ms 25520 KB Output is correct
10 Correct 202 ms 23912 KB Output is correct
11 Correct 194 ms 21188 KB Output is correct
12 Correct 227 ms 22764 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 24668 KB Output is correct
2 Correct 199 ms 31664 KB Output is correct
3 Correct 14 ms 10612 KB Output is correct
4 Correct 255 ms 25564 KB Output is correct
5 Correct 260 ms 26812 KB Output is correct
6 Correct 278 ms 25200 KB Output is correct
7 Correct 494 ms 32152 KB Output is correct
8 Correct 484 ms 33256 KB Output is correct
9 Correct 469 ms 30536 KB Output is correct
10 Correct 569 ms 33000 KB Output is correct
11 Correct 490 ms 29828 KB Output is correct
12 Correct 511 ms 32852 KB Output is correct
13 Correct 324 ms 26988 KB Output is correct
14 Correct 525 ms 34048 KB Output is correct
15 Correct 516 ms 33260 KB Output is correct
16 Correct 407 ms 31696 KB Output is correct
17 Correct 464 ms 30568 KB Output is correct
18 Correct 303 ms 26020 KB Output is correct