Submission #55843

#	Time	Username	Problem	Language	Result	Execution time	Memory
55843		Yehezkiel	Pipes (CEOI15_pipes)	C++11	80 / 100	4986 ms	16956 KiB

pipes

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

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 10 / 10