oj.uz

Submission #129727

# Submission time Handle Problem Language Result Execution time Memory
129727 2019-07-13T05:51:22 Z 임유진(#3141) 전압 (JOI14_voltage) C++14
100 / 100
 167 ms 15608 KB 
#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 100005
#define MAXM 200005

int A[MAXM], B[MAXM];
vector<int> ed[MAXN];
int par[MAXN], dep[MAXN], dp[MAXN];
bool chk[MAXN];
int odd;

void dfs(int x) {
	bool p = false;
	chk[x] = true;
	//printf("dfs(%d), par[x] = %d\n", x, par[x]);
	for(auto a : ed[x]) {
		//printf("a = %d\n", a);
		if(!p && a == par[x]) {
			p = true;
			continue;
		}
		if(chk[a] && dep[a] < dep[x]) {
			if((dep[x] - dep[a]) % 2 == 0) {
				dp[x]++;
				dp[a]--;
				odd++;
			}
			else {
				dp[x]--;
				dp[a]++;
			}
		}
		else if(!chk[a]) {
			par[a] = x;
			dep[a] = dep[x] + 1;
			dfs(a);
		}
	}
	//printf("end dfs(%d)\n", x);
}

void dfs2(int x) {
	chk[x] = true;
	for(auto a : ed[x]) if(!chk[a]) {
		dfs2(a);
		dp[x] += dp[a];
	}
}

int main() {
	int N, M;

	//freopen("input.txt", "r", stdin);

	scanf("%d%d", &N, &M);
	for(int i = 0; i < M; i++) scanf("%d%d", A + i, B + i);

	for(int i = 0; i < M; i++) {
		ed[A[i]].push_back(B[i]);
		ed[B[i]].push_back(A[i]);
	}
	
	/*
	for(int i = 1; i <= N; i++) {
		for(auto a : ed[i]) printf("%d ", a);
		printf("\n");
	}
	*/

	for(int i = 1; i <= N; i++) if(!chk[i]) dfs(i);
	for(int i = 1; i <= N; i++) chk[i] = false;
	for(int i = 1; i <= N; i++) if(!chk[i]) dfs2(i);

	int ans = 0;
	for(int i = 1; i <= N; i++) if(par[i] != 0 && dp[i] == odd) ans++;
	//for(int i = 1; i <= N; i++) printf("%d ", dp[i]);
	printf("%d", ans + (odd == 1 ? 1 : 0));
	return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
voltage.cpp:59:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 0; i < M; i++) scanf("%d%d", A + i, B + i);
                             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 9072 KB Output is correct
2 Correct 103 ms 11640 KB Output is correct
3 Correct 51 ms 9072 KB Output is correct
4 Correct 103 ms 12700 KB Output is correct
5 Correct 10 ms 3576 KB Output is correct
6 Correct 87 ms 10620 KB Output is correct
7 Correct 107 ms 13732 KB Output is correct
8 Correct 104 ms 13644 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8556 KB Output is correct
2 Correct 46 ms 13688 KB Output is correct
3 Correct 45 ms 13688 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 62 ms 10104 KB Output is correct
6 Correct 69 ms 9080 KB Output is correct
7 Correct 93 ms 11144 KB Output is correct
8 Correct 99 ms 12088 KB Output is correct
9 Correct 97 ms 12036 KB Output is correct
10 Correct 100 ms 10872 KB Output is correct
11 Correct 68 ms 9080 KB Output is correct
12 Correct 100 ms 10236 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 10984 KB Output is correct
2 Correct 72 ms 15608 KB Output is correct
3 Correct 6 ms 2808 KB Output is correct
4 Correct 116 ms 11896 KB Output is correct
5 Correct 97 ms 12564 KB Output is correct
6 Correct 115 ms 11744 KB Output is correct
7 Correct 149 ms 14100 KB Output is correct
8 Correct 146 ms 14456 KB Output is correct
9 Correct 142 ms 13132 KB Output is correct
10 Correct 149 ms 14952 KB Output is correct
11 Correct 142 ms 13332 KB Output is correct
12 Correct 164 ms 15096 KB Output is correct
13 Correct 123 ms 12912 KB Output is correct
14 Correct 167 ms 15608 KB Output is correct
15 Correct 149 ms 15028 KB Output is correct
16 Correct 130 ms 14444 KB Output is correct
17 Correct 119 ms 13048 KB Output is correct
18 Correct 109 ms 13160 KB Output is correct