oj.uz

Submission #25768

# Submission time Handle Problem Language Result Execution time Memory
25768 2017-06-24T05:37:12 Z kdh9949 전압 (JOI14_voltage) C++14
100 / 100
 339 ms 22672 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;
			if(!t) dc++;
			S[t].upd(ps[i.x], -1);
			S[t].upd(ps[x], 1);
		}
		else if(!vis[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]);
		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;
			}
		}
	}
	fill(vis + 1, vis + n + 1, 0);
	if(!cr){
		int rans = 0;
		for(int i = 1; i <= n; i++){
			if(vis[i]) continue;
			ans = dc = 0;
			g(i, -1);
			if(dc > 1) ans = 0;
			else if(dc == 1) ans = 1;
			f(i);
			rans += ans;
		}
		printf("%d\n", rans);
	}
	else{
		g(cr, -1);
		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:64: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:66: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 3 ms 10452 KB Output is correct
2 Correct 0 ms 10320 KB Output is correct
3 Correct 3 ms 10460 KB Output is correct
4 Correct 3 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 0 ms 10452 KB Output is correct
11 Correct 0 ms 10452 KB Output is correct
12 Correct 0 ms 10452 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 15572 KB Output is correct
2 Correct 199 ms 19104 KB Output is correct
3 Correct 59 ms 15572 KB Output is correct
4 Correct 186 ms 20080 KB Output is correct
5 Correct 16 ms 11008 KB Output is correct
6 Correct 169 ms 17120 KB Output is correct
7 Correct 216 ms 21084 KB Output is correct
8 Correct 213 ms 21084 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 15572 KB Output is correct
2 Correct 79 ms 21084 KB Output is correct
3 Correct 66 ms 21084 KB Output is correct
4 Correct 0 ms 10320 KB Output is correct
5 Correct 133 ms 17276 KB Output is correct
6 Correct 153 ms 15732 KB Output is correct
7 Correct 189 ms 18248 KB Output is correct
8 Correct 183 ms 19544 KB Output is correct
9 Correct 189 ms 19060 KB Output is correct
10 Correct 199 ms 18052 KB Output is correct
11 Correct 153 ms 15732 KB Output is correct
12 Correct 179 ms 17336 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 16596 KB Output is correct
2 Correct 129 ms 22672 KB Output is correct
3 Correct 3 ms 10320 KB Output is correct
4 Correct 189 ms 18860 KB Output is correct
5 Correct 216 ms 19632 KB Output is correct
6 Correct 243 ms 18744 KB Output is correct
7 Correct 283 ms 20568 KB Output is correct
8 Correct 306 ms 21216 KB Output is correct
9 Correct 279 ms 19600 KB Output is correct
10 Correct 316 ms 21396 KB Output is correct
11 Correct 303 ms 19208 KB Output is correct
12 Correct 339 ms 21540 KB Output is correct
13 Correct 176 ms 17704 KB Output is correct
14 Correct 296 ms 21896 KB Output is correct
15 Correct 309 ms 21440 KB Output is correct
16 Correct 279 ms 21008 KB Output is correct
17 Correct 309 ms 18956 KB Output is correct
18 Correct 233 ms 19440 KB Output is correct