Submission #109667

#	Time	Username	Problem	Language	Result	Execution time	Memory
109667		jangwonyoung	Alternating Current (BOI18_alternating)	C++14	100 / 100	428 ms	15576 KiB

alternating

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
const int N=1e5+1,M=1e5+1;
int n,m;
int u[M],v[M];
vector<int>add[M];
bool in[M];
set<int>s;
vector<int>adj[M];
int col[M];
bool ok=true;
void dfs(int id){
	for(auto cur:adj[id]){
		if(col[cur]==col[id]) ok=false;
		if(!col[cur]){
			col[cur]=3-col[id];
			dfs(cur);
		}
	}
}
int lz[262144],mi[262144];
void push(int id){
	lz[id*2]+=lz[id];
	mi[id*2]+=lz[id];
	lz[id*2+1]+=lz[id];
	mi[id*2+1]+=lz[id];
	lz[id]=0;
}
void upd(int id,int l,int r,int ql,int qr,int v){
	if(l>qr || r<ql) return;
	if(ql<=l && r<=qr){
		lz[id]+=v;mi[id]+=v;return;
	}
	push(id);
	int mid=(l+r)/2;
	upd(id*2,l,mid,ql,qr,v);upd(id*2+1,mid+1,r,ql,qr,v);
	mi[id]=min(mi[id*2],mi[id*2+1]);
}
int qry(int id,int l,int r,int ql,int qr){
	if(l>qr || r<ql) return 1e9;
	if(ql<=l && r<=qr) return mi[id];
	push(id);
	int mid=(l+r)/2;
	return min(qry(id*2,l,mid,ql,qr),qry(id*2+1,mid+1,r,ql,qr));
}
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=1; i<=m ;i++){
		cin >> u[i] >> v[i];
		add[u[i]-1].pb(i);add[v[i]].pb(i);
		if(u[i]>v[i] || u[i]==1) s.insert(i),in[i]=true;
	}
	for(int i=1; i<=n ;i++){
		if(s.size()<2) return cout << "impossible\n",0;
		if(s.size()==2){
			int x=*s.begin(),y=*s.rbegin();
			adj[x].pb(y);adj[y].pb(x);
		}
		for(auto cur:add[i]){
			if(in[cur]) in[cur]=false,s.erase(cur);
			else in[cur]=true,s.insert(cur);
		}
	}
	for(int i=1; i<=m ;i++){
		if(!col[i]){col[i]=1;dfs(i);}
		if(col[i]==1){
			if(u[i]<=v[i]) upd(1,1,n,u[i],v[i],1);
			else upd(1,1,n,u[i],n,1),upd(1,1,n,1,v[i],1);
		}
	}
	if(!ok) return cout << "impossible\n",0;
	for(int i=1; i<=m ;i++){
		if(col[i]!=1){cout << "0";continue;}
		int val;
		if(u[i]<=v[i]) val=qry(1,1,n,u[i],v[i]);
		else val=min(qry(1,1,n,u[i],n),qry(1,1,n,1,v[i]));
		if(val==1){cout << "1";continue;}
		if(u[i]<=v[i]) upd(1,1,n,u[i],v[i],-1);
		else upd(1,1,n,u[i],n,-1),upd(1,1,n,1,v[i],-1);
		cout << "0";
	}
	cout << endl;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 22 / 22
• Subtask 4: 19 / 19
• Subtask 5: 26 / 26