oj.uz

Submission #25762

# Submission time Handle Problem Language Result Execution time Memory
25762 2017-06-24T05:31:05 Z 김동현(#1079) 전압 (JOI14_voltage) C++14
55 / 100
 203 ms 22668 KB 
#include <bits/stdc++.h>
using namespace std;

struct E{ int x, i; };

int n, m, vis[100010], cr, d[100010], ps[100010], pe[100010], cnt, dc, fl, ans;
vector<E> e[100010];
vector<int> t[100010];

void T_T(){ puts("0"); exit(0); }

void col(int x, int c){
	vis[x] = c;
	for(auto &i : e[x]){
		if(vis[i.x] && vis[i.x] != 3 - c) fl = 0;
		else if(!vis[i.x]) col(i.x, 3 - c);
	}
}

const int sz = 131072;
struct Seg{
	int dat[2 * sz];
	void upd(int x, int v){ for(x += sz; x; x /= 2) dat[x] += v; }
	int get(int s, int e){
		int ret = 0;
		for(s += sz, e += sz; s <= e; s /= 2, e /= 2){
			if(s % 2 == 1) ret += dat[s++];
			if(e % 2 == 0) ret += dat[e--];
		}
		return ret;
	}
} S[2];

void g(int x, int p){
	vis[x] = 1;
	ps[x] = ++cnt;
	for(auto &i : e[x]){
		if(i.i == p) continue;
		if(vis[i.x] && d[i.x] < d[x]){
			int t = (d[i.x] + d[x]) & 1;
			//printf("back %d - %d : %d\n", x, i.x, t);
			if(!t) dc++;
			S[t].upd(ps[i.x], -1);
			S[t].upd(ps[x], 1);
		}
		else if(!vis[i.x]){
			//printf("go %d -> %d\n", x, i.x);
			t[x].push_back(i.x);
			d[i.x] = d[x] + 1;
			g(i.x, i.i);
		}
	}
	pe[x] = cnt;
}

void f(int x){
	for(auto &i : t[x]){
		f(i);
		int t0 = S[0].get(ps[i], pe[i]);
		int t1 = S[1].get(ps[i], pe[i]);
		//printf("%d -> %d : %d / %d\n", x, i, t0, t1);
		if(t0 == dc && !t1) ans++;
	}
}

int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0, x, y; i < m; i++){
		scanf("%d%d", &x, &y);
		e[x].push_back({y, i});
		e[y].push_back({x, i});
	}
	for(int i = 1; i <= n; i++){
		if(!vis[i]){
			fl = 1;
			col(i, 1);
			if(!fl){
				if(cr) T_T();
				cr = i;
			}
		}
	}
	if(!cr) cr = 1;
	fill(vis + 1, vis + n + 1, 0);
	g(cr, -1);
	//printf("%d %d\n", dc, ans);
	if(dc > 1) ans = 0;
	else if(dc == 1) ans = 1;
	f(cr);
	printf("%d\n", ans);
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:67:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
voltage.cpp:69:24: 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 10452 KB Output is correct
2 Correct 0 ms 10320 KB Output is correct
3 Correct 0 ms 10460 KB Output is correct
4 Correct 0 ms 10452 KB Output is correct
5 Correct 0 ms 10452 KB Output is correct
6 Correct 0 ms 10452 KB Output is correct
7 Correct 3 ms 10452 KB Output is correct
8 Correct 0 ms 10452 KB Output is correct
9 Correct 3 ms 10452 KB Output is correct
10 Correct 3 ms 10452 KB Output is correct
11 Correct 3 ms 10452 KB Output is correct
12 Correct 3 ms 10452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 15572 KB Output is correct
2 Correct 123 ms 19104 KB Output is correct
3 Correct 79 ms 15572 KB Output is correct
4 Correct 183 ms 20072 KB Output is correct
5 Correct 16 ms 11012 KB Output is correct
6 Correct 196 ms 17124 KB Output is correct
7 Correct 203 ms 21084 KB Output is correct
8 Correct 173 ms 21088 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 15572 KB Output is correct
2 Correct 73 ms 21088 KB Output is correct
3 Correct 83 ms 21088 KB Output is correct
4 Correct 0 ms 10320 KB Output is correct
5 Correct 119 ms 17276 KB Output is correct
6 Correct 146 ms 15732 KB Output is correct
7 Correct 103 ms 18252 KB Output is correct
8 Correct 183 ms 19536 KB Output is correct
9 Correct 189 ms 19056 KB Output is correct
10 Correct 186 ms 18048 KB Output is correct
11 Correct 129 ms 15732 KB Output is correct
12 Correct 196 ms 17344 KB Output is correct

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 16596 KB Output is correct
2 Correct 143 ms 22668 KB Output is correct
3 Incorrect 0 ms 10320 KB Output isn't correct
4 Halted 0 ms 0 KB -