oj.uz

Submission #41070

# Submission time Handle Problem Language Result Execution time Memory
41070 2018-02-12T10:54:17 Z IvanC 전압 (JOI14_voltage) C++14
100 / 100
 375 ms 64020 KB 
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
const int MAXN = 1e5 + 10;
const int MAXM = 2*1e5 + 10;
int e1[MAXM],e2[MAXM],pai[MAXN],ligapai[MAXN],peso[MAXN],N,M,ans;
int possivel,last,oldw[MAXM],oldz[MAXM],oldpai[MAXM],oldliga[MAXM],oldpeso[MAXM],oldpossivel[MAXM];
int find(int x){
	if(x == pai[x]) return x;
	return find(pai[x]);
}
int parity(int x){
	if(x == pai[x]) return 0;
	return (ligapai[x] ^ parity(pai[x]));
}
void join(int x,int y){
	int w = find(x), z = find(y),px = parity(x),py = parity(y);
	if(peso[w] < peso[z]){
		swap(w,z);
		swap(px,py);
		swap(x,y);
	}
	last++;
	oldw[last] = w;
	oldz[last] = z;
	oldpai[last] = pai[z];
	oldliga[last] = ligapai[z];
	oldpeso[last] = peso[w];
	oldpossivel[last] = possivel;
	if(w == z){
		if(px == py) possivel = 0;
		return;
	}
	pai[z] = w;
	peso[w] += peso[z];
	if(px == py) ligapai[z] = 1;
	else ligapai[z] = 0;
}
void undo(){
	int w = oldw[last] , z = oldz[last];
	peso[w] = oldpeso[last];
	pai[z] = oldpai[last];
	ligapai[z] = oldliga[last];
	possivel = oldpossivel[last];
	last--; 
}
void divide_and_conquer(int ini,int fim){
	if(!possivel) return;
	if(ini == fim){
		if(possivel){
			if(find(e1[ini]) != find(e2[ini])) ans++;
			else if(parity(e1[ini]) == parity(e2[ini])) ans++;
		}
		return;
	}
	int meio = (ini+fim)/2;
	for(int i = meio + 1;i<=fim;i++){
		join(e1[i],e2[i]);
	}
	divide_and_conquer(ini,meio);
	for(int i = meio + 1;i<=fim;i++){
		undo();
	}
	for(int i = ini;i<=meio;i++){
		join(e1[i],e2[i]);
	}
	divide_and_conquer(meio+1,fim);
	for(int i = ini;i<=meio;i++){
		undo();
	}
}
int main(){
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=N;i++){
		pai[i] = i;
		peso[i] = 1;
		ligapai[i] = 0;
	}
	possivel = 1;
	for(int i = 1;i<=M;i++){
		scanf("%d %d",&e1[i],&e2[i]);
	}
	divide_and_conquer(1,M);
	printf("%d\n",ans);
	return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:73:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
                      ^
voltage.cpp:81:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&e1[i],&e2[i]);
                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 496 KB Output is correct
3 Correct 3 ms 580 KB Output is correct
4 Correct 2 ms 580 KB Output is correct
5 Correct 3 ms 688 KB Output is correct
6 Correct 3 ms 700 KB Output is correct
7 Correct 4 ms 844 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 3 ms 844 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 2 ms 860 KB Output is correct
12 Correct 2 ms 892 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 6344 KB Output is correct
2 Correct 205 ms 7484 KB Output is correct
3 Correct 50 ms 8660 KB Output is correct
4 Correct 51 ms 9696 KB Output is correct
5 Correct 16 ms 9696 KB Output is correct
6 Correct 196 ms 10960 KB Output is correct
7 Correct 204 ms 12208 KB Output is correct
8 Correct 209 ms 13412 KB Output is correct

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 14052 KB Output is correct
2 Correct 49 ms 15308 KB Output is correct
3 Correct 48 ms 16360 KB Output is correct
4 Correct 1 ms 16360 KB Output is correct
5 Correct 176 ms 16568 KB Output is correct
6 Correct 152 ms 18536 KB Output is correct
7 Correct 203 ms 19716 KB Output is correct
8 Correct 185 ms 20868 KB Output is correct
9 Correct 202 ms 21892 KB Output is correct
10 Correct 195 ms 23060 KB Output is correct
11 Correct 85 ms 24324 KB Output is correct
12 Correct 147 ms 25380 KB Output is correct

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 30132 KB Output is correct
2 Correct 118 ms 32436 KB Output is correct
3 Correct 4 ms 32436 KB Output is correct
4 Correct 206 ms 32436 KB Output is correct
5 Correct 230 ms 32436 KB Output is correct
6 Correct 177 ms 33448 KB Output is correct
7 Correct 353 ms 38528 KB Output is correct
8 Correct 312 ms 40964 KB Output is correct
9 Correct 288 ms 43152 KB Output is correct
10 Correct 292 ms 45456 KB Output is correct
11 Correct 77 ms 45456 KB Output is correct
12 Correct 100 ms 50092 KB Output is correct
13 Correct 132 ms 52492 KB Output is correct
14 Correct 375 ms 54776 KB Output is correct
15 Correct 80 ms 56356 KB Output is correct
16 Correct 286 ms 59212 KB Output is correct
17 Correct 327 ms 61588 KB Output is correct
18 Correct 262 ms 64020 KB Output is correct