oj.uz

Submission #129722

# Submission time Handle Problem Language Result Execution time Memory
129722 2019-07-13T05:49:44 Z 박상수(#3145) 전압 (JOI14_voltage) C++14
100 / 100
 172 ms 15412 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_set>
#include <bitset>
#include <time.h>
#include <limits.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define Fi first
#define Se second
#define pb push_back
#define szz(x) (int)x.size()
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
typedef tuple<int, int, int> t3;

int N, M;
vector <pii> E[100010];
int vis[100010], dep[100010];
int chke[200020], val[100010], tv;
void dfs(int x, int fe) {
	if(fe != -1) chke[x] = 1;
	vis[x] = 1;
	for(pii e : E[x]) if(e.Fi != fe) {
		if(vis[e.Se] == 0) {
			dep[e.Se] = dep[x] + 1;
			dfs(e.Se, e.Fi);
			val[x] += val[e.Se];
		}
		else if(vis[e.Se] == 1) {
			if((dep[x] - dep[e.Se]) % 2) {
				val[x] -= 1;
				val[e.Se] += 1;
			}
			else {
				val[x] += 1;
				val[e.Se] -= 1;
				++tv;
			}
		}
	}
	vis[x] = 2;
}

int main() {
	scanf("%d%d", &N, &M);
	rep(i, M) {
		int x, y;
		scanf("%d%d", &x, &y);
		E[x].pb(pii(i, y));
		E[y].pb(pii(i, x));
	}
	int rt[100010] = {};
	for(int i=1;i<=N;i++) if(vis[i] == 0) dfs(i, -1), rt[i] = 1;
	int ans = (tv == 1);
	for(int i=1;i<=N;i++) if(!rt[i]) ans += (val[i] == tv);
	printf("%d\n", ans);
	return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:61: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:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &x, &y);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 9376 KB Output is correct
2 Correct 85 ms 11640 KB Output is correct
3 Correct 57 ms 9324 KB Output is correct
4 Correct 86 ms 12680 KB Output is correct
5 Correct 10 ms 3960 KB Output is correct
6 Correct 101 ms 11132 KB Output is correct
7 Correct 90 ms 13688 KB Output is correct
8 Correct 91 ms 13560 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 8812 KB Output is correct
2 Correct 46 ms 13560 KB Output is correct
3 Correct 46 ms 13596 KB Output is correct
4 Correct 4 ms 3064 KB Output is correct
5 Correct 61 ms 10460 KB Output is correct
6 Correct 70 ms 9464 KB Output is correct
7 Correct 80 ms 11384 KB Output is correct
8 Correct 93 ms 12008 KB Output is correct
9 Correct 97 ms 12312 KB Output is correct
10 Correct 87 ms 11220 KB Output is correct
11 Correct 82 ms 9456 KB Output is correct
12 Correct 94 ms 10640 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 10596 KB Output is correct
2 Correct 81 ms 15408 KB Output is correct
3 Correct 5 ms 3420 KB Output is correct
4 Correct 89 ms 12276 KB Output is correct
5 Correct 91 ms 12984 KB Output is correct
6 Correct 93 ms 12168 KB Output is correct
7 Correct 151 ms 14200 KB Output is correct
8 Correct 149 ms 14412 KB Output is correct
9 Correct 153 ms 13304 KB Output is correct
10 Correct 169 ms 15220 KB Output is correct
11 Correct 165 ms 13320 KB Output is correct
12 Correct 165 ms 15320 KB Output is correct
13 Correct 136 ms 12640 KB Output is correct
14 Correct 167 ms 15412 KB Output is correct
15 Correct 172 ms 15224 KB Output is correct
16 Correct 143 ms 14308 KB Output is correct
17 Correct 142 ms 13464 KB Output is correct
18 Correct 122 ms 12868 KB Output is correct