oj.uz

Submission #55931

# Submission time Handle Problem Language Result Execution time Memory
55931 2018-07-09T07:47:54 Z Yehezkiel Pipes (CEOI15_pipes) C++17
100 / 100
 2984 ms 15292 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define gc getchar_unlocked
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
typedef pair<int,int> pii;
const int MAXN=100000;
inline void scan(int &angka){
	char input=gc();
	while(!('0'<=input&&input<='9'))	input=gc();
	angka=0;
	while('0'<=input&&input<='9')	angka=(angka<<1)+(angka<<3)+input-'0',input=gc();
}
int n,m,i;

const int logn=17;
vector <pii> edgelist;
vector <int> node[MAXN+1];
int kandungan[MAXN+1],par[MAXN+1][logn]={},delta[MAXN+1]={},depth[MAXN+1]={};
bool report[MAXN+1];

void dfs(const int &now){
	for(int i=1;i<logn;++i)
		par[now][i]=par[par[now][i-1]][i-1];
	
	for(int i=0;i<node[now].size();++i)
	{
		int tempDfs=(edgelist[node[now][i]].fi==now)?edgelist[node[now][i]].se:edgelist[node[now][i]].fi;
		if(tempDfs==par[now][0])
			continue;
		par[tempDfs][0]=now;
		depth[tempDfs]=depth[now]+1;
		kandungan[tempDfs]=node[now][i];
		dfs(tempDfs);
	}
}
inline int lca(int u,int v){
	if(depth[u]>depth[v])
		swap(u,v);
	int beda=depth[v]-depth[u];
	/*for(int i=0;i<logn;++i)
		if(beda&(1<<i))*/
	while(beda)
	{
		v=par[v][__builtin_popcount((beda&-beda)-1)];
		beda-=beda&-beda;
	}
	if(u==v)
		return u;
	for(i=logn-1;i>=0;--i)
	{
		if(par[u][i]!=par[v][i])
		{
			u=par[u][i];
			v=par[v][i];
		}
	}
	return par[u][0];
}
int findReport(const int &now){
	int status=delta[now];
	delta[now]=0;			//done urusannya, ngereport karena butuh di reset
	for(int i=0;i<node[now].size();++i)
	{
		int tempDfs=(edgelist[node[now][i]].fi==now)?edgelist[node[now][i]].se:edgelist[node[now][i]].fi;
		if(tempDfs==par[now][0])
			continue;
		status+=findReport(tempDfs);
	}
	if(status!=0&&kandungan[now]!=-1)				//part of cycle berarti
		report[kandungan[now]]=false;
	return status;
}

class UFDS{
	private:
	int p[MAXN+1],size[MAXN+1];
	int finds(const int &u){
		if(p[u]!=u)
			p[u]=finds(p[u]);
		return p[u];
	}
	public:
	inline void inis(){
		for(int i=1;i<=n;++i)
		{
			p[i]=i;
			size[i]=1;
		}
	}
	inline bool boss(const int &pos){
		return p[pos]==pos;
	}
	inline bool connected(const int &u,const int &v){
		return finds(u)==finds(v);
	}
	inline void gabung(int &u,int &v){
		int rootU=finds(u);
		int rootV=finds(v);
		if(rootU==rootV)
			return;
		if(size[rootU]<size[rootV])
		{
			swap(rootU,rootV);
			swap(u,v);
		}
		size[rootU]+=size[rootV];
		p[rootV]=rootU;
		
		findReport(rootV);
		par[v][0]=u;
		depth[v]=depth[u]+1;
		kandungan[v]=edgelist.size();
		dfs(v);
	}
};
UFDS disjointSet;
int main()
{	
	scan(n),scan(m);
	disjointSet.inis();
	
	int u,v;
	for(int i=1;i<=m;++i)
	{
		scan(u),scan(v);
		if(disjointSet.connected(u,v))
		{
			delta[lca(u,v)]-=2;
			delta[u]++;
			delta[v]++;
		}
		else
		{
			disjointSet.gabung(u,v);
			node[u].eb(edgelist.size());
			node[v].eb(edgelist.size());
			report[edgelist.size()]=true;
			edgelist.eb(u,v);
		}
	}
	for(i=1;i<=n;++i)
		if(disjointSet.boss(i))
			findReport(i);
	for(i=0;i<edgelist.size();++i)
	{
		if(!report[i])
			continue;
		printf("%d %d\n",edgelist[i].fi,edgelist[i].se);
	}
}

Compilation message

pipes.cpp: In function 'void dfs(const int&)':
pipes.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<node[now].size();++i)
              ~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int findReport(const int&)':
pipes.cpp:68:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<node[now].size();++i)
              ~^~~~~~~~~~~~~~~~~
pipes.cpp: In function 'int main()':
pipes.cpp:150:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<edgelist.size();++i)
          ~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3328 KB Output is correct
2 Correct 7 ms 3328 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3072 KB Output is correct
2 Correct 59 ms 3164 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 3968 KB Output is correct
2 Correct 171 ms 3960 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 5632 KB Output is correct
2 Correct 268 ms 6412 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 927 ms 11860 KB Output is correct
2 Correct 732 ms 11908 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1271 ms 12892 KB Output is correct
2 Correct 775 ms 12924 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1566 ms 15272 KB Output is correct
2 Correct 1423 ms 15292 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2476 ms 15224 KB Output is correct
2 Correct 2079 ms 15292 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2984 ms 14604 KB Output is correct
2 Correct 1642 ms 15212 KB Output is correct