oj.uz

Submission #306375

# Submission time Handle Problem Language Result Execution time Memory
306375 2020-09-25T10:22:57 Z starusc Teoretičar (COCI18_teoreticar) C++11
0 / 130
 9479 ms 48228 KB 
//starusc
#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	return f==1?x:-x;
}
#define ll long long
#define rit register int
const int N=5e5+4;
const ll inf=0x3f3f3f3f3f3f3f3f;
namespace wll{
	struct edge{
		int v,nxt;
		ll w;
	}e[N<<2];
	int first[N],cur[N],cnt=1,tot=2,s=1,t=2;
	inline void add(int u,int v,ll w){
		e[++cnt].v=v;e[cnt].w=w;
		e[cnt].nxt=first[u];first[u]=cnt;
		e[++cnt].v=u;e[cnt].w=0;
		e[cnt].nxt=first[v];first[v]=cnt;
	}
	inline void clear(){
		memset(first,0,sizeof(int)*(tot+1));
		cnt=1;
		tot=2;
	}
	int dep[N];
	queue<int>qq;
	inline bool bfs(){
		memset(dep,0x3f,sizeof(int)*(tot+1));
		dep[s]=1;
		while(!qq.empty())qq.pop();
		qq.push(s);
		while(!qq.empty()){
			int x=qq.front();qq.pop();
			for(rit i=first[x],v;i;i=e[i].nxt){
				v=e[i].v;
				if(dep[v]!=0x3f3f3f3f||!e[i].w)continue;
				dep[v]=dep[x]+1;
				if(v==t)return 1;
				qq.push(v);
			}
		}
		return 0;
	}
	ll dfs(int x,ll f){
		if(x==t||!f)return f;
		ll used=0,w;
		for(int &i=cur[x],v;i;i=e[i].nxt){
			v=e[i].v;
			if(!e[i].w||dep[v]!=dep[x]+1)continue;
			w=dfs(v,min(f,e[i].w));
			if(!w)continue;
			e[i].w-=w;e[i^1].w+=w;
			f-=w;used+=w;
			if(!f)return used; 
		}
		return used;
	}
	void dinic(){
		ll flow=0;
		while(bfs()){
			memcpy(cur,first,sizeof(int)*(tot+1));
			flow+=dfs(s,inf); 
		}
	}
}
int col[N],to[N],deg[N];
struct node{
	int u,v,id;
}q[N],q1[N],q2[N];
inline void solve(int ql,int qr,int l,int r){
	if(l>r)return;
	if(ql==qr){
		for(rit i=l;i<=r;i++)col[q[i].id]=ql;
		return;
	}
	int mid=(qr-ql+1)>>1,cl=0,cr=0,fl=1;
	for(rit i=l,u,v;i<=r;i++){
		u=q[i].u;v=q[i].v;
		if(!to[u])to[u]=++wll::tot;
		if(!to[v])to[v]=++wll::tot;
		deg[u]++;deg[v]++;
		fl&=(deg[u]<=mid&&deg[v]<=mid);
	}
	if(fl){
		for(rit i=l,u,v;i<=r;i++){
			u=q[i].u;v=q[i].v;
			to[u]=to[v]=deg[u]=deg[v]=0;
		}
		solve(ql,(ql+qr)>>1,l,r);
		return;
	}
	for(rit i=l;i<=r;i++){
		wll::add(to[q[i].u],to[q[i].v],1);
	}
	++wll::tot;
	for(rit i=l,u,v;i<=r;i++){
		u=q[i].u;v=q[i].v;
		if(to[u]){
			wll::add(wll::s,to[u],mid);
			if(mid*2-deg[u])wll::add(to[u],wll::tot,mid*2-deg[u]);
			to[u]=deg[u]=0;
			cl++;
		}
		if(to[v]){
			wll::add(to[v],wll::t,mid);
			if(mid*2-deg[v])wll::add(wll::tot,to[v],mid*2-deg[v]);
			to[v]=deg[v]=0;
			cr++;
		}
	}
	if(cl<cr)wll::add(wll::s,wll::tot,(ll)(cr-cl)*mid);
	if(cl>cr)wll::add(wll::tot,wll::t,(ll)(cl-cr)*mid);
	wll::dinic();
	cl=cr=0;
	for(rit i=l;i<=r;i++){
		if(wll::e[(i-l+1)<<1].w)q1[++cl]=q[i];
		else q2[++cr]=q[i];
	}
	wll::clear();
	for(rit i=1;i<=cl;i++)q[i+l-1]=q1[i];
	for(rit i=1;i<=cr;i++)q[r-i+1]=q2[i];
	mid=(ql+qr)>>1;
	solve(ql,mid,l,l+cl-1);
	solve(mid+1,qr,r-cr+1,r);
} 
int L,R,m,mx,len;
int main(){
	int clo=clock(); 
	L=read();R=read();m=read();
	for(rit i=1,u,v;i<=m;i++){
		q[i].u=u=read();q[i].v=v=read()+L;q[i].id=i;
		deg[u]++;deg[v]++;
	}
	for(rit i=1;i<=L+R;i++)mx=max(mx,deg[i]);
	len=1;
	while(len<mx)len<<=1;
	memset(deg,0,sizeof(deg));
	solve(1,len,1,m);
	for(rit i=1;i<=m;i++)cout<<col[i]<<"\n";
	cerr<<(double)(clock()-clo)/CLOCKS_PER_SEC<<"\n";
	return (0-0);
}
/*
3 3 5
1 1
1 2
2 2
2 3
3 3

2 4 4
1 1
1 2
1 3
2 4
*/

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2304 KB Integer 2 violates the range [1, 1]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2336 KB Integer 29 violates the range [1, 23]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 3072 KB Integer 4 violates the range [1, 1]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 2944 KB Integer 177 violates the range [1, 159]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 9479 ms 39364 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 9285 ms 39412 KB Integer 4 violates the range [1, 2]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2083 ms 48228 KB Integer 41864 violates the range [1, 41863]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1973 ms 38060 KB Integer 496 violates the range [1, 328]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 930 ms 31192 KB Integer 4082 violates the range [1, 4036]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1324 ms 31320 KB Integer 4088 violates the range [1, 4085]
2 Halted 0 ms 0 KB -