oj.uz

Submission #25818

# Submission time Handle Problem Language Result Execution time Memory
25818 2017-06-24T08:42:30 Z kajebiii 전압 (JOI14_voltage) C++14
100 / 100
 343 ms 31028 KB 
#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define REPO(i,n) for(int (i)=1; (i)<=(int)(n); (i)++)
#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 1e5 + 100, LOG_N = 20;

int N, M;
vector<int> Ed[MAX_N], Tr[MAX_N];
int P[LOG_N][MAX_N], Ix[MAX_N], IN, Co[MAX_N], D[MAX_N];
vector<pi> List;
void dfs(int v, int p) {
	P[0][v] = p;
	Ix[v] = ++IN;
	Co[v] = 1 - Co[p]; D[v] = D[p] + 1;
	for(int w : Ed[v]) {
		if(Ix[w] == 0) dfs(w, v), Tr[v].push_back(w);
		else if(Ix[v] < Ix[w]) List.push_back(pi(v, w));
	}
}
int getLCA(int a, int b) {
	if(D[a] < D[b]) swap(a, b);
	for(int p=0; p<LOG_N; p++) if((D[a] - D[b]) & (1<<p)) a = P[p][a];
	if(a == b) return a;
	for(int p=LOG_N-1; p>=0; p--) if(P[p][a] != P[p][b])
		a = P[p][a], b = P[p][b];
	return P[0][a];
}
int Val[MAX_N];
void getUp(int v, int p) {
	for(int w : Tr[v]) {
		getUp(w, v);
		Val[v] += Val[w];
	}
}
int main() {
	cin >> N >> M;
	for(int i=0; i<M; i++) {
		int x, y; scanf("%d%d", &x, &y);
		Ed[x].push_back(y);
		Ed[y].push_back(x);
	}
	for(int i=1; i<=N; i++) if(Ix[i] == 0) dfs(i, 0);
	for(int p=1; p<LOG_N; p++) for(int i=1; i<=N; i++) P[p][i] = P[p-1][P[p-1][i]];

	int same = 0;
	for(pi &e : List) {
		int x, y; tie(x, y) = e;
		int val = -1;
		if(Co[x] == Co[y]) val = +1, same++;
		int l = getLCA(x, y);
		Val[x] += val; Val[y] += val; Val[l] -= val * 2;
	}
	for(int i=1; i<=N; i++) if(P[0][i] == 0) getUp(i, 0);

	int ans = 0;
	if(same == 1) ans++;
	for(int i=1; i<=N; i++) if(P[0][i] != 0)
		if(Val[i] == same) ans++;
	printf("%d\n", ans);
	return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:49:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int x, y; scanf("%d%d", &x, &y);
                                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 16232 KB Output is correct
2 Correct 3 ms 16096 KB Output is correct
3 Correct 0 ms 16228 KB Output is correct
4 Correct 3 ms 16096 KB Output is correct
5 Correct 0 ms 16228 KB Output is correct
6 Correct 6 ms 16228 KB Output is correct
7 Correct 0 ms 16228 KB Output is correct
8 Correct 0 ms 16228 KB Output is correct
9 Correct 3 ms 16228 KB Output is correct
10 Correct 6 ms 16228 KB Output is correct
11 Correct 0 ms 16228 KB Output is correct
12 Correct 3 ms 16228 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 20840 KB Output is correct
2 Correct 129 ms 26688 KB Output is correct
3 Correct 86 ms 20840 KB Output is correct
4 Correct 149 ms 28304 KB Output is correct
5 Correct 13 ms 16756 KB Output is correct
6 Correct 153 ms 23380 KB Output is correct
7 Correct 153 ms 29984 KB Output is correct
8 Correct 169 ms 29984 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 20840 KB Output is correct
2 Correct 46 ms 29984 KB Output is correct
3 Correct 46 ms 29988 KB Output is correct
4 Correct 0 ms 16096 KB Output is correct
5 Correct 106 ms 24348 KB Output is correct
6 Correct 136 ms 20980 KB Output is correct
7 Correct 149 ms 25036 KB Output is correct
8 Correct 143 ms 27412 KB Output is correct
9 Correct 123 ms 26380 KB Output is correct
10 Correct 159 ms 24704 KB Output is correct
11 Correct 96 ms 20980 KB Output is correct
12 Correct 159 ms 23520 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 22888 KB Output is correct
2 Correct 83 ms 31028 KB Output is correct
3 Correct 3 ms 16096 KB Output is correct
4 Correct 173 ms 26096 KB Output is correct
5 Correct 166 ms 27384 KB Output is correct
6 Correct 163 ms 25792 KB Output is correct
7 Correct 289 ms 26912 KB Output is correct
8 Correct 323 ms 28892 KB Output is correct
9 Correct 279 ms 25980 KB Output is correct
10 Correct 336 ms 28376 KB Output is correct
11 Correct 283 ms 25832 KB Output is correct
12 Correct 343 ms 28388 KB Output is correct
13 Correct 213 ms 25144 KB Output is correct
14 Correct 283 ms 29972 KB Output is correct
15 Correct 336 ms 28432 KB Output is correct
16 Correct 239 ms 28456 KB Output is correct
17 Correct 289 ms 26732 KB Output is correct
18 Correct 199 ms 26616 KB Output is correct