oj.uz

Submission #129724

# Submission time Handle Problem Language Result Execution time Memory
129724 2019-07-13T05:50:19 Z 임유진(#3141) 전압 (JOI14_voltage) C++14
10 / 100
 3 ms 632 KB 
#include <stdio.h>
#include <vector>

using namespace std;

#define MAXN 1005
#define MAXM 2005

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 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 3 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 504 KB Output is correct
11 Correct 3 ms 504 KB Output is correct
12 Correct 3 ms 376 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3 ms 376 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -