oj.uz

Submission #55843

# Submission time Handle Problem Language Result Execution time Memory
55843 2018-07-09T05:45:39 Z Yehezkiel Pipes (CEOI15_pipes) C++11
80 / 100
 4986 ms 16956 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
typedef pair<int,int> pii;
const int batasMemori=120000;
const int MAXN=100000;
int n,m;
class UFDS{
	private:
	int par[MAXN+5];
	int finds(int u){
		if(par[u]!=u)
			par[u]=finds(par[u]);
		return par[u];
	}
	public:
	void inis(){
		for(int i=1;i<=n;i++)
			par[i]=i;
	}
	bool connected(int u,int v){
		return finds(u)==finds(v);
	}
	void gabung(int u,int v){
		u=finds(u);
		v=finds(v);
		if(u==v)
			return;
		par[u]=v;
	}
};
UFDS disjointSet;

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

void dfs(int now,int _par,int _kandugan,int _depth){
	par[0][now]=_par;
	depth[now]=_depth;
	kandungan[now]=_kandugan;
	for(auto v:node[now])
		if(v.fi!=_par)
			dfs(v.fi,now,v.se,depth[now]+1);
}
void buildLCA(){
	for(int i=0;i<logn;i++)
		for(int j=1;j<=n;j++)
			par[i][j]=0;
	for(int i=1;i<=n;i++)
	{
		if(par[0][i]==0)
			dfs(i,0,-1,0);
	}
	for(int i=1;i<logn;i++)
	{
		for(int j=1;j<=n;j++)
			par[i][j]=par[i-1][par[i-1][j]];
	}
}
int lca(int u,int v){
	if(depth[u]>depth[v])
		swap(u,v);
	int beda=depth[v]-depth[u];
	for(int i=logn-1;i>=0;i--)
		if(beda&(1<<i))
			v=par[i][v];
	if(u==v)
		return u;
	for(int i=logn-1;i>=0;i--)
	{
		if(par[i][u]!=par[i][v])
		{
			u=par[i][u];
			v=par[i][v];
		}
	}
	return par[0][u];
}
int findReport(int now){
	int status=delta[now];
	for(auto v:node[now])
	{
		if(v.fi==par[0][now])
			continue;
		status+=findReport(v.fi);
	}
	if(status!=0&&kandungan[now]!=-1)				//part of cycle berarti
		report[kandungan[now]]=false;
	return status;
}
void doPending(){
	for(auto isi:pending)
	{
		int LCA=lca(isi.fi,isi.se);
		delta[LCA]-=2;
		delta[isi.fi]++;
		delta[isi.se]++;
	}
	for(int i=1;i<=n;i++)
	{
		if(par[0][i]==0)			//berarti root
			findReport(i);
	}
}
void solve(){
	for(int i=1;i<=n;i++)
		delta[i]=0;
	buildLCA();
	doPending();
}
void reset(){
	pending.clear();
}
int main()
{
	memset(report,true,sizeof(report));
	
	scanf("%d%d",&n,&m);
	disjointSet.inis();
	
	int u,v;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		if(disjointSet.connected(u,v))
			pending.eb(u,v);
		else
		{
			disjointSet.gabung(u,v);
			node[u].eb(v,edgelist.size());
			node[v].eb(u,edgelist.size());
			edgelist.eb(u,v);
		}
		
		if(i==m||i%batasMemori==0)
		{
			//do it
			solve();
			reset();
		}
	}
	for(int 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 'int main()':
pipes.cpp:149:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<edgelist.size();i++)
              ~^~~~~~~~~~~~~~~~
pipes.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
pipes.cpp:131:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&u,&v);
   ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 3584 KB Output is correct
2 Correct 8 ms 3584 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 4336 KB Output is correct
2 Correct 175 ms 4360 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 371 ms 5092 KB Output is correct
2 Correct 424 ms 5128 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 6892 KB Output is correct
2 Correct 564 ms 7468 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1210 ms 12780 KB Output is correct
2 Correct 1039 ms 12680 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2322 ms 14528 KB Output is correct
2 Correct 1905 ms 13876 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3537 ms 16956 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 4641 ms 16952 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
2 Halted 0 ms 0 KB -

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4986 ms 16144 KB Output is correct
2 Correct 4205 ms 16136 KB Output is correct