oj.uz

Submission #63246

# Submission time Handle Problem Language Result Execution time Memory
63246 2018-08-01T06:57:05 Z 정원준(#1835) Alternating Current (BOI18_alternating) C++11
0 / 100
 350 ms 18252 KB 
#include <bits/stdc++.h>
#define L int
#define inf 123456
using namespace std;

int ans[100010],preans[100010];
int n,m;
vector<int>v[100010],lines[100010];
int chk[100010];

struct S{
	int s,e,ord;
}a[100010];

int tr[400040],one[400040],two[400040];

int onetr[400040],twotr[400040];

void update(int now,int S,int E,int s,int e,int val,int num){
	if(S>e||E<s) return;
	if(s<=S&&E<=e)
	{
		tr[now]+=val;
		return;
	}
	int mid=(S+E)/2;
	update(now*2,S,mid,s,e,val,num);
	update(now*2+1,mid+1,E,s,e,val,num);
}

void initone(int now,int S,int E){
	one[now]=inf;
	if(S==E) return;
	int mid=(S+E)/2;
	initone(now*2,S,mid);
	initone(now*2+1,mid+1,E);
}
void updateone(int now,int S,int E,int s,int e,int val,int num){
	if(S>e||E<s) return;
	//printf("%d %d %d %d %d %d %d\n",now,S,E,s,e,val,num);
	if(s<=S&&E<=e)
	{
		one[now]=min(one[now],num);
		return;
	}
	int mid=(S+E)/2;
	updateone(now*2,S,mid,s,e,val,num);
	updateone(now*2+1,mid+1,E,s,e,val,num);
}
void updatetwo(int now,int S,int E,int s,int e,int val,int num){
	if(S>e||E<s) return;
	if(s<=S&&E<=e)
	{
		two[now]=max(two[now],num);
		return;
	}
	int mid=(S+E)/2;
	updatetwo(now*2,S,mid,s,e,val,num);
	updatetwo(now*2+1,mid+1,E,s,e,val,num);
}

int sum(int now,int S,int E,int loc){
	if(S>loc||E<loc) return 0;
	if(S==E) return tr[now];
	int mid=(S+E)/2;
	return tr[now]+sum(now*2,S,mid,loc)+sum(now*2+1,mid+1,E,loc);
}


int getone(int now,int S,int E,int loc){
	//printf("%d %d %d %d\n",now,S,E,loc);
	if(S>loc||E<loc) return inf;
	if(S==E) return one[now];
	int mid=(S+E)/2;
	return min(one[now],min(getone(now*2,S,mid,loc),getone(now*2+1,mid+1,E,loc)));
}


int gettwo(int now,int S,int E,int loc){
	//printf("%d %d %d %d\n",now,S,E,loc);
	if(S>loc||E<loc) return 0;
	if(S==E) return two[now];
	int mid=(S+E)/2;
	return max(two[now],max(gettwo(now*2,S,mid,loc),gettwo(now*2+1,mid+1,E,loc)));
}

void oneup(int now,int S,int E,int s,int e,int val){
	if(S>e||E<s) return;
	if(s<=S&&E<=e)
	{
		onetr[now]+=val;
		return;
	}
	int mid=(S+E)/2;
	oneup(now*2,S,mid,s,e,val);
	oneup(now*2+1,mid+1,E,s,e,val);
}

void twoup(int now,int S,int E,int s,int e,int val){
	if(S>e||E<s) return;
	if(s<=S&&E<=e)
	{
		twotr[now]+=val;
		return;
	}
	int mid=(S+E)/2;
	twoup(now*2,S,mid,s,e,val);
	twoup(now*2+1,mid+1,E,s,e,val);
}

int oneget(int now,int S,int E,int loc){
	if(S>loc||E<loc) return 0;
	if(onetr[now]) return 1;
	if(S==E) return 0;
	L mid=(S+E)/2;
	return oneget(now*2,S,mid,loc)||oneget(now*2+1,mid+1,E,loc);
}
int twoget(int now,int S,int E,int loc){
	if(S>loc||E<loc) return 0;
	if(twotr[now]) return 1;
	if(S==E) return 0;
	L mid=(S+E)/2;
	return twoget(now*2,S,mid,loc)||twoget(now*2+1,mid+1,E,loc);
}

void E(){
	puts("impossible");
	exit(0);
}

void dfs(int x,int col){
	int i;
	preans[x]=col;
	for(i=0;i<v[x].size();i++)
	{
		if(preans[v[x][i]]==col) E();
		if(chk[v[x][i]])
		{
			chk[v[x][i]]=0;
			dfs(v[x][i],3-col);
		}
	}
}

void coloring(int x,int col){
	if(col==1)
	{
		if(a[x].s<=a[x].e)
		{
			oneup(1,1,n,a[x].s,a[x].e,1);
		}
		else
		{
			oneup(1,1,n,a[x].s,n,1);
			oneup(1,1,n,1,a[x].e,1);	
		}
	}
	else
	{
		if(a[x].s<=a[x].e)
		{
			twoup(1,1,n,a[x].s,a[x].e,1);
		}
		else
		{
			twoup(1,1,n,a[x].s,n,1);
			twoup(1,1,n,1,a[x].e,1);	
		}
	}
	
	int i;
	for(i=0;i<v[x].size();i++)
	{
		if(!ans[v[x][i]])
		{
			ans[v[x][i]]=3-col;
			coloring(v[x][i],3-col);
		}
	}
}

int main()
{
	srand((int)time(NULL));
	scanf("%d %d",&n,&m);
	L i,j;
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&a[i].s,&a[i].e);
		lines[a[i].s].push_back(i);
		a[i].ord=i;
		if(a[i].s<=a[i].e) update(1,1,n,a[i].s,a[i].e,1,i);
		else
		{
			update(1,1,n,1,a[i].e,1,i);
			update(1,1,n,a[i].s,n,1,i);
		}
	}
	initone(1,1,n);
	for(i=1;i<=m;i++)
	{
		if(a[i].s<=a[i].e) updateone(1,1,n,a[i].s,a[i].e,1,i);
		else
		{
			updateone(1,1,n,1,a[i].e,1,i);
			updateone(1,1,n,a[i].s,n,1,i);
		}
	}
	for(i=1;i<=m;i++)
	{
		if(a[i].s<=a[i].e) updatetwo(1,1,n,a[i].s,a[i].e,1,i);
		else
		{
			updatetwo(1,1,n,1,a[i].e,1,i);
			updatetwo(1,1,n,a[i].s,n,1,i);
		}
	}
	/*for(i=1;i<=4*n;i++)
	{
		printf("%lld %lld\n",i,one[i]);
	}*/
	
	for(i=1;i<=n;i++)
	{
		L temp=sum(1,1,n,i);
		if(temp<=1) E();
		else if(temp<=2)
		{
			L temp1=getone(1,1,n,i),temp2=gettwo(1,1,n,i);
			//printf("%d %d %d\n",i,temp1,temp2);
			v[temp1].push_back(temp2);
			v[temp2].push_back(temp1);
			chk[temp1]=chk[temp2]=1;
		}
	}
	for(i=1;i<=m;i++)
	{
		if(chk[i])
		{
			chk[i]=0;
			dfs(i,1);
		}
	}
	/*for(i=1;i<=m;i++)
	{
		if(ans[i]==1)
		{
			if(a[i].s<=a[i].e)
			{
				oneup(1,1,n,a[i].s,a[i].e,1);
			}
			else
			{
				oneup(1,1,n,1,a[i].s,1);
				oneup(1,1,n,a[i].e,n,1);
			}
		}
		else
		{
			if(a[i].s<=a[i].e)
			{
				twoup(1,1,n,a[i].s,a[i].e,1);
			}
			else
			{
				twoup(1,1,n,1,a[i].s,1);
				twoup(1,1,n,a[i].e,n,1);
			}
		}
		//printf("%d ",ans[i]);
	}*/
	for(i=1;i<=n;i++)
	{
		L temp1=oneget(1,1,n,i);
		L temp2=twoget(1,1,n,i);
		if(!temp1)
		{
			for(j=0;j<lines[i].size();i++)
			{
				if(!ans[lines[i][j]])
				{
					if(preans[lines[i][j]])
					{
						ans[lines[i][j]]=1;
						coloring(lines[i][j],1);
					}
					else
					{
						ans[lines[i][j]]=1;
						if(a[lines[i][j]].s<=a[lines[i][j]].e)
						{
							oneup(1,1,n,a[lines[i][j]].s,a[lines[i][j]].e,1);
						}
						else
						{
							oneup(1,1,n,a[lines[i][j]].s,n,1);
							oneup(1,1,n,1,a[lines[i][j]].e,1);	
						}
					}
					break;
				}
			}
			temp2=twoget(1,1,n,i);
		}
		if(!temp2)
		{
			for(j=0;j<lines[i].size();i++)
			{
				if(!ans[lines[i][j]])
				{
					if(preans[lines[i][j]])
					{
						ans[lines[i][j]]=2;
						coloring(lines[i][j],2);
					}
					else
					{
						ans[lines[i][j]]=2;
						if(a[lines[i][j]].s<=a[lines[i][j]].e)
						{
							twoup(1,1,n,a[lines[i][j]].s,a[lines[i][j]].e,1);
						}
						else
						{
							twoup(1,1,n,a[lines[i][j]].s,n,1);
							twoup(1,1,n,1,a[lines[i][j]].e,1);	
						}
					}
					break;
				}
			}
		}
	}
	for(i=1;i<=m;i++)
	{
		if(preans[i]&&!ans[i])
		{
			coloring(i,rand()%2+1);
		}
	}
	for(i=1;i<=m;i++)
	{
		if(ans[i]==1) printf("0");
		else if(ans[i]==2) printf("1");
		else if(rand()%2) printf("0");
		else printf("1");
	}
	
}

Compilation message

alternating.cpp: In function 'void dfs(int, int)':
alternating.cpp:134:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
alternating.cpp: In function 'void coloring(int, int)':
alternating.cpp:172:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
alternating.cpp: In function 'int main()':
alternating.cpp:278:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<lines[i].size();i++)
            ~^~~~~~~~~~~~~~~~
alternating.cpp:307:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<lines[i].size();i++)
            ~^~~~~~~~~~~~~~~~
alternating.cpp:185:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
alternating.cpp:189:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].s,&a[i].e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5076 KB Output is correct
2 Correct 8 ms 5096 KB Output is correct
3 Correct 7 ms 5276 KB Output is correct
4 Correct 7 ms 5276 KB Output is correct
5 Correct 7 ms 5276 KB Output is correct
6 Incorrect 7 ms 5276 KB no wires in direction 0 between segments 7 and 7
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5076 KB Output is correct
2 Correct 8 ms 5096 KB Output is correct
3 Correct 7 ms 5276 KB Output is correct
4 Correct 7 ms 5276 KB Output is correct
5 Correct 7 ms 5276 KB Output is correct
6 Incorrect 7 ms 5276 KB no wires in direction 0 between segments 7 and 7
7 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5076 KB Output is correct
2 Correct 8 ms 5096 KB Output is correct
3 Correct 7 ms 5276 KB Output is correct
4 Correct 7 ms 5276 KB Output is correct
5 Correct 7 ms 5276 KB Output is correct
6 Incorrect 7 ms 5276 KB no wires in direction 0 between segments 7 and 7
7 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 8008 KB Output is correct
2 Correct 85 ms 8008 KB Output is correct
3 Correct 76 ms 10412 KB Output is correct
4 Correct 84 ms 10668 KB Output is correct
5 Correct 350 ms 18016 KB Output is correct
6 Correct 169 ms 18016 KB Output is correct
7 Incorrect 336 ms 18252 KB no wires in direction 0 between segments 763 and 763
8 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5076 KB Output is correct
2 Correct 8 ms 5096 KB Output is correct
3 Correct 7 ms 5276 KB Output is correct
4 Correct 7 ms 5276 KB Output is correct
5 Correct 7 ms 5276 KB Output is correct
6 Incorrect 7 ms 5276 KB no wires in direction 0 between segments 7 and 7
7 Halted 0 ms 0 KB -