oj.uz

Submission #221437

# Submission time Handle Problem Language Result Execution time Memory
221437 2020-04-10T05:37:54 Z bensonlzl 전압 (JOI14_voltage) C++14
100 / 100
 160 ms 19192 KB 
#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pi;

vector<pi> AdjList[100005];
int colour[100005], visit[100005], depth[100005];
int badup[100005], goodup[100005];
int badlow[100005], goodlow[100005];
int badlep[100005], goodlep[100005];
int baduep[100005], gooduep[100005];
int par[100005];
int N, M, A, B;
int total_bad = 0;
int usable = 0;

void dfs(int x, int p){
	par[x] = p;
	//cout << x << ' ' << p << '\n';
	visit[x] = 1;
	for (auto it : AdjList[x]){
		int v = it.first, e = it.second;
		if (e == p) continue;
		if (visit[v]){
			if (depth[x] > depth[v]){
				if (colour[x] == colour[v]){
					badlep[x]++;
					badup[x]++;
					baduep[v]++;
					total_bad++;
				}
				else{
					goodlep[x]++;
					goodup[x]++;
					gooduep[v]++;
				}
			}
		}
		else{
			depth[v] = depth[x] + 1;
			colour[v] = 1 - colour[x];
			dfs(v,e);
			badup[x] += badup[v];
			goodup[x] += goodup[v];
		}
	}
	badup[x] -= baduep[x];
	goodup[x] -= gooduep[x];
}

void check_vertex(int x, int p){
	visit[x] = 1;
	//cout << "CHECKING " << x << ' ' << p << '\n';
	if (p != -1){
		if (total_bad == badup[x]){
			if (goodup[x] == 0){
				usable++;
				//cout << p << " CASE 1A\n";
			}
		}
	}
	for (auto it : AdjList[x]){
		int v = it.first, e = it.second;
		if (p == e) continue;
		if (par[v] == e){
			check_vertex(v,e);
		}
		else{
			if (depth[x] < depth[v]) continue;
			if (total_bad == 1 && colour[v] == colour[x]){
				usable++;
				//cout << "CASE 2A\n";
			}
		}
	}
	//cout << "ENDING " << x << ' ' << p << '\n';
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= M; ++i){
		cin >> A >> B;
		AdjList[A].push_back(pi(B,i));
		AdjList[B].push_back(pi(A,i));
	}
	for (int i = 1; i <= N; ++i){
		if (!visit[i]){
			depth[i] = 0;
			colour[i] = 0;
			dfs(i,-1);
		} 
	}
	for (int i = 1; i <= N; ++i){
		visit[i] = 0;
	}
	for (int i = 1; i <= N; ++i){
		if (!visit[i]){
			check_vertex(i,-1);
		} 
	}
	/*
	for (int i = 1; i <= N; ++i){
		cout << badup[i] << ' ' << goodup[i] << '\n';
	}
	*/
	cout << usable << '\n';
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 10092 KB Output is correct
2 Correct 86 ms 12920 KB Output is correct
3 Correct 49 ms 10092 KB Output is correct
4 Correct 89 ms 14328 KB Output is correct
5 Correct 11 ms 3712 KB Output is correct
6 Correct 80 ms 11896 KB Output is correct
7 Correct 86 ms 15608 KB Output is correct
8 Correct 86 ms 15608 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 9716 KB Output is correct
2 Correct 48 ms 15584 KB Output is correct
3 Correct 49 ms 15608 KB Output is correct
4 Correct 6 ms 2688 KB Output is correct
5 Correct 63 ms 12024 KB Output is correct
6 Correct 70 ms 9976 KB Output is correct
7 Correct 134 ms 13176 KB Output is correct
8 Correct 87 ms 14072 KB Output is correct
9 Correct 86 ms 14200 KB Output is correct
10 Correct 87 ms 12876 KB Output is correct
11 Correct 79 ms 10236 KB Output is correct
12 Correct 94 ms 11640 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 11748 KB Output is correct
2 Correct 86 ms 19064 KB Output is correct
3 Correct 8 ms 4992 KB Output is correct
4 Correct 99 ms 14328 KB Output is correct
5 Correct 115 ms 15608 KB Output is correct
6 Correct 93 ms 14432 KB Output is correct
7 Correct 152 ms 17148 KB Output is correct
8 Correct 147 ms 17528 KB Output is correct
9 Correct 158 ms 15992 KB Output is correct
10 Correct 157 ms 18296 KB Output is correct
11 Correct 141 ms 15992 KB Output is correct
12 Correct 160 ms 18424 KB Output is correct
13 Correct 126 ms 15208 KB Output is correct
14 Correct 146 ms 18808 KB Output is correct
15 Correct 155 ms 19192 KB Output is correct
16 Correct 141 ms 17256 KB Output is correct
17 Correct 129 ms 16124 KB Output is correct
18 Correct 104 ms 15080 KB Output is correct