Submission #306216

#	Time	Username	Problem	Language	Result	Execution time	Memory
306216		andremfq	전압 (JOI14_voltage)	C++17	100 / 100	364 ms	10232 KiB

voltage

// Ivan Carvalho
// Voltage - JOI SC 2014
#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],parent[MAXN],connectParent[MAXN],weight[MAXN],N,M,ans;
int possible,last,oldW[MAXM],oldz[MAXM],oldParent[MAXM],oldConnection[MAXM],oldWeight[MAXM],oldPossible[MAXM];

int find(int x){
	if(x == parent[x]) return x;
	return find(parent[x]);
}

int parity(int x){
	if(x == parent[x]) return 0;
	return (connectParent[x] ^ parity(parent[x]));
}

void join(int x,int y){
	
	int w = find(x), z = find(y),px = parity(x),py = parity(y);
	
	if(weight[w] < weight[z]){
		swap(w,z);
		swap(px,py);
		swap(x,y);
	}
	
	last++;
	oldW[last] = w;
	oldz[last] = z;
	oldParent[last] = parent[z];
	oldConnection[last] = connectParent[z];
	oldWeight[last] = weight[w];
	oldPossible[last] = possible;
	
	if(w == z){
		if(px == py) possible = 0;
		return;
	}

	parent[z] = w;
	weight[w] += weight[z];

	if(px == py) connectParent[z] = 1;
	else connectParent[z] = 0;

}

void undo(){
	int w = oldW[last] , z = oldz[last];
	weight[w] = oldWeight[last];
	parent[z] = oldParent[last];
	connectParent[z] = oldConnection[last];
	possible = oldPossible[last];
	last--; 
}

void divide_and_conquer(int lo,int hi){
	
	if(lo == hi){
		if(possible){
			if(find(e1[lo]) != find(e2[lo])) ans++;
			else if(parity(e1[lo]) == parity(e2[lo])) ans++;
		}
		return;
	}
	
	int mid = (lo+hi)/2;
	for(int i = mid + 1;i<=hi;i++){
		join(e1[i],e2[i]);
	}
	
	divide_and_conquer(lo,mid);
	
	for(int i = mid + 1;i<=hi;i++){
		undo();
	}
	
	for(int i = lo;i<=mid;i++){
		join(e1[i],e2[i]);
	}
	
	divide_and_conquer(mid+1,hi);
	
	for(int i = lo;i<=mid;i++){
		undo();
	}

}

int main(){
	
	scanf("%d %d",&N,&M);
	
	for(int i = 1;i<=N;i++){
		parent[i] = i;
		weight[i] = 1;
		connectParent[i] = 0;
	}
	
	possible = 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 (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45