oj.uz

Submission #41015

# Submission time Handle Problem Language Result Execution time Memory
41015 2018-02-11T13:15:52 Z IvanC 전압 (JOI14_voltage) C++14
10 / 100
 1000 ms 6472 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],lazypai[MAXN],lazyligapai[MAXN],versao[MAXN],iteracao,possivel,lazypossivel,N,M;
int find(int x){
	if(x == pai[x]) return x;
	int y = pai[x];
	pai[x] = find(y);
	ligapai[x] = (ligapai[y] ^ ligapai[x]);
	return pai[x];
}
int parity(int x){
	find(x); // Just for updating the distance
	return ligapai[x];
}
inline void join(int x,int y){
	int w = find(x),z = find(y);
	int px = parity(x),py = parity(y);
	if(w == z){
		if(px == py) possivel = 0;
		return;
	}
	if(w < z){
		swap(w,z);
		swap(px,py);
		swap(x,y);
	}
	pai[z] = w;
	if(px == py) ligapai[z] = 1;
	else ligapai[z] = 0;
}
int lazyfind(int x){
	if(versao[x] != iteracao){
		versao[x] = iteracao;
		lazypai[x] = pai[x];
		lazyligapai[x] = ligapai[x];
	}
	if(x == lazypai[x]) return x;
	int y = lazypai[x];
	lazypai[x] = lazyfind(y);
	lazyligapai[x] = (lazyligapai[y] ^ lazyligapai[x]);
	return lazypai[x];
}
int lazyparity(int x){
	lazyfind(x); // Just for updating the distance
	return lazyligapai[x];
}
inline void lazyjoin(int x,int y){
	int w = lazyfind(x),z = lazyfind(y);
	int px = lazyparity(x),py = lazyparity(y);
	if(w == z){
		if(px == py) lazypossivel = 0;
		return;
	}
	if(w < z){
		swap(w,z);
		swap(px,py);
		swap(x,y);
	}
	lazypai[z] = w;
	if(px == py) lazyligapai[z] = 1;
	else lazyligapai[z] = 0;
}
int bipartite_check(int lo,int hi){
	for(int i = 1;i<=N;i++){
		pai[i] = i;
		ligapai[i] = 0;
	}
	possivel = 1;
	for(int i = 1;i<=M && possivel;i++){
		if(lo <= i && i <= hi) continue;
		join(e1[i],e2[i]);
	}
	if(!possivel) return 0;
	int ans = 0;
	for(int davez = lo;davez<=hi;davez++){
		iteracao++;
		lazypossivel = possivel;
		for(int i = lo;i<=hi && lazypossivel;i++){
			if(i == davez) continue;
			lazyjoin(e1[i],e2[i]);
		}
		if(!lazypossivel) continue;
		if(lazyfind(e1[davez]) == lazyfind(e2[davez]) && lazyparity(e1[davez]) != lazyparity(e2[davez])) continue;
		ans++;
	}
	return ans;
}
int main(){
	scanf("%d %d",&N,&M);
	for(int i = 1;i<=M;i++){
		scanf("%d %d",&e1[i],&e2[i]);
	}
	int ans = 0,BUCKET = 4*(int)ceil(sqrt(M));
	for(int lo = 1,hi = BUCKET;lo <= M;lo += BUCKET,hi+=BUCKET) ans += bipartite_check(lo, min(hi,M) );
	printf("%d\n",ans);
	return 0;
}

Compilation message

voltage.cpp: In function 'int main()':
voltage.cpp:92: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:94: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 15 ms 376 KB Output is correct
2 Correct 14 ms 376 KB Output is correct
3 Correct 3 ms 424 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 17 ms 476 KB Output is correct
6 Correct 17 ms 476 KB Output is correct
7 Correct 17 ms 476 KB Output is correct
8 Correct 5 ms 476 KB Output is correct
9 Correct 19 ms 476 KB Output is correct
10 Correct 22 ms 532 KB Output is correct
11 Correct 2 ms 536 KB Output is correct
12 Correct 2 ms 548 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 3364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 35.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 3364 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 45.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1060 ms 6472 KB Time limit exceeded
2 Halted 0 ms 0 KB -