oj.uz

답안 #129746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
129746 2019-07-13T07:07:32 Z 김세빈(#3138) 전압 (JOI14_voltage) C++14
100 / 100
 199 ms 21724 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

vector <ll> G[101010];
ll V[404040], X[202020];
ll D[101010], S[101010];
bool chk[101010];
ll n, m, k, ans;

void dfs(ll p, ll r)
{
	chk[p] = 1;
	
	for(ll &t: G[p]){
		if(t == r) continue;
		else if(!chk[V[t ^ 1]]){
			D[V[t ^ 1]] = D[p] + 1;
			dfs(V[t ^ 1], t ^ 1);
			S[p] += S[V[t ^ 1]];
		}
		else if(D[V[t ^ 1]] < D[p]){
			if(D[p] - D[V[t ^ 1]] & 1){
				X[t >> 1] += 1e9;
				S[p] += 1e9; S[V[t ^ 1]] -= 1e9;
			}
			else{
				X[t >> 1] ++; k ++;
				S[p] ++; S[V[t ^ 1]] --;
			}
		}
	}
	
	if(r != -1){
		X[r >> 1] = S[p];
	}
}

int main()
{
	ll i;
	
	scanf("%lld%lld", &n, &m);
	
	for(i=0; i<m+m; i++){
		scanf("%lld", V + i);
		G[V[i]].push_back(i);
	}
	
	for(i=1; i<=n; i++){
		if(!chk[i]) dfs(i, -1);
	}
	
	for(i=0; i<m; i++){
		if(X[i] == k) ans ++;
	}
	
	printf("%lld\n", ans);
	
	return 0;
}

Compilation message

voltage.cpp: In function 'void dfs(ll, ll)':
voltage.cpp:25:12: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
    if(D[p] - D[V[t ^ 1]] & 1){
       ~~~~~^~~~~~~~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld%lld", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~
voltage.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", V + i);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2936 KB Output is correct
2 Correct 5 ms 2808 KB Output is correct
3 Correct 4 ms 2808 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 5 ms 2940 KB Output is correct
6 Correct 5 ms 2936 KB Output is correct
7 Correct 5 ms 2936 KB Output is correct
8 Correct 5 ms 2812 KB Output is correct
9 Correct 7 ms 2916 KB Output is correct
10 Correct 6 ms 2936 KB Output is correct
11 Correct 5 ms 2936 KB Output is correct
12 Correct 5 ms 2812 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 11072 KB Output is correct
2 Correct 105 ms 14560 KB Output is correct
3 Correct 60 ms 11124 KB Output is correct
4 Correct 110 ms 15956 KB Output is correct
5 Correct 11 ms 3960 KB Output is correct
6 Correct 97 ms 13532 KB Output is correct
7 Correct 108 ms 17400 KB Output is correct
8 Correct 100 ms 17276 KB Output is correct

Subtask #3
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 10600 KB Output is correct
2 Correct 62 ms 17240 KB Output is correct
3 Correct 57 ms 17316 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 80 ms 12792 KB Output is correct
6 Correct 91 ms 11640 KB Output is correct
7 Correct 110 ms 14200 KB Output is correct
8 Correct 101 ms 15196 KB Output is correct
9 Correct 103 ms 15352 KB Output is correct
10 Correct 102 ms 14016 KB Output is correct
11 Correct 87 ms 11640 KB Output is correct
12 Correct 93 ms 13096 KB Output is correct

Subtask #4
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 15324 KB Output is correct
2 Correct 114 ms 21724 KB Output is correct
3 Correct 6 ms 2936 KB Output is correct
4 Correct 131 ms 15452 KB Output is correct
5 Correct 113 ms 16460 KB Output is correct
6 Correct 111 ms 15352 KB Output is correct
7 Correct 182 ms 19708 KB Output is correct
8 Correct 191 ms 20056 KB Output is correct
9 Correct 194 ms 18584 KB Output is correct
10 Correct 194 ms 20928 KB Output is correct
11 Correct 189 ms 18680 KB Output is correct
12 Correct 199 ms 21012 KB Output is correct
13 Correct 154 ms 17776 KB Output is correct
14 Correct 188 ms 21316 KB Output is correct
15 Correct 191 ms 21112 KB Output is correct
16 Correct 172 ms 19944 KB Output is correct
17 Correct 166 ms 18684 KB Output is correct
18 Correct 138 ms 18148 KB Output is correct