Submission #41015

#	Time	Username	Problem	Language	Result	Execution time	Memory
41015		IvanC	전압 (JOI14_voltage)	C++14	10 / 100	1060 ms	6472 KiB

voltage

#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 (stderr)

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 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 35
• Subtask 4: 0 / 45