제출 #222635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
222635		jamielim	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	491 ms	31080 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN=100005;
int n,m;
pair<int,int> edge[MAXN];
vector<pair<int,int> > adj[MAXN];

int par[MAXN];
int dep[MAXN];
int low[MAXN];
bool vis[MAXN];
bool bri[MAXN];
int ctr=0;
void dfs(int x){
	vis[x]=1;
	dep[x]=low[x]=ctr++;
	for(int i=0;i<(int)adj[x].size();i++){
		int y=adj[x][i].first;
		if(!vis[y]){ //not yet visited
			par[y]=x;
			dfs(y);
			if(low[y]>dep[x])bri[adj[x][i].second]=1;
			low[x]=min(low[x],low[y]);
		}else if(y!=par[x])low[x]=min(low[x],dep[y]); //visited and is not parent
	}
}
 
int scc[MAXN];
int c=0;
void comp(int x){
	scc[x]=c;
	for(int i=0;i<(int)adj[x].size();i++){
		if(!bri[adj[x][i].second]&&scc[adj[x][i].first]==-1)comp(adj[x][i].first);
	}
}

vector<pair<int,int> > adj2[MAXN];

pair<int,int> q[MAXN];
vector<pair<int,int> > r;
int pa[MAXN][19],idx[MAXN];
int ldep[MAXN];
void dfs2(int x){
	vis[x]=1;
	for(int i=0;i<(int)(adj2[x].size());i++){
		int y=adj2[x][i].first;
		if(!vis[y]){
			pa[y][0]=x;idx[y]=adj2[x][i].second;
			ldep[y]=ldep[x]+1;
			dfs2(y);
		}
	}
}
int lca(int x,int y){
    if(x==y)return x;
    if(ldep[x]<ldep[y])swap(x,y);
    for(int i=18;i>=0;i--){
        if(pa[x][i]!=-1&&ldep[pa[x][i]]>=ldep[y])x=pa[x][i];
    }
    if(x==y)return x;
    for(int i=18;i>=0;i--){
        if(pa[x][i]!=pa[y][i]){x=pa[x][i];y=pa[y][i];}
    }
    return pa[x][0];
}
 
int ans[MAXN]; //0 B, 1 R, -1 L
void dir(int x,int y,int d){
	if(x==y)return;
	if(ans[idx[x]]!=0)return;
	int a=edge[idx[x]].first,b=edge[idx[x]].second;
	if(x==scc[a]){
		ans[idx[x]]=d;dir(scc[b],y,d);
	}else{
		ans[idx[x]]=-d;dir(scc[a],y,d);
	}
}
 
int main(){
	scanf("%d%d",&n,&m);
	memset(par,-1,sizeof(par));memset(dep,-1,sizeof(dep));memset(low,-1,sizeof(low));
	memset(scc,-1,sizeof(scc));
	memset(pa,-1,sizeof(pa));memset(idx,-1,sizeof(idx));memset(ldep,-1,sizeof(ldep));
	int a,b;
	for(int i=0;i<m;i++){
		scanf("%d%d",&a,&b);a--;b--;edge[i]=make_pair(a,b);
		adj[a].push_back(make_pair(b,i));adj[b].push_back(make_pair(a,i));
	}
	for(int i=0;i<n;i++)if(!vis[i])dfs(i);
	//for(int i=0;i<m;i++)if(bri[i])printf("1 ");else printf("0 ");printf("\n");
	for(int i=0;i<n;i++)if(scc[i]==-1){comp(i);c++;}
	for(int i=0;i<m;i++){
		if(bri[i]){
			a=edge[i].first,b=edge[i].second;
			adj2[scc[a]].push_back(make_pair(scc[b],i));adj2[scc[b]].push_back(make_pair(scc[a],i));
		}
	}
	//for(int i=0;i<n;i++)printf("%d ",scc[i]);printf("\n");
	for(int i=0;i<c;i++)vis[i]=0; for(int i=0;i<c;i++)if(!vis[i]){ldep[i]=0;dfs2(i);}
	for(int i=1;i<18;i++)for(int j=0;j<c;j++)if(pa[j][i-1]!=-1)pa[j][i]=pa[pa[j][i-1]][i-1];
	int p;scanf("%d",&p);
	for(int i=0;i<p;i++){
		scanf("%d%d",&q[i].first,&q[i].second);q[i].first--;q[i].second--;
		if(scc[q[i].first]==scc[q[i].second])continue;
		r.push_back(make_pair(ldep[lca(scc[q[i].first],scc[q[i].second])],i));
	}
	sort(r.begin(),r.end());
	for(int i=0;i<(int)r.size();i++){
		a=q[r[i].second].first,b=q[r[i].second].second;
		//printf("%d->%d->%d\n",a,r[i].first,b);
		int l=lca(scc[a],scc[b]);
		dir(scc[a],l,1);
		dir(scc[b],l,-1);
	}
	for(int i=0;i<m;i++){
		if(ans[i]==0)printf("B");
		else if(ans[i]==1)printf("R");
		else printf("L");
	}
}

컴파일 시 표준 에러 (stderr) 메시지

oneway.cpp: In function 'int main()':
oneway.cpp:100:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  for(int i=0;i<c;i++)vis[i]=0; for(int i=0;i<c;i++)if(!vis[i]){ldep[i]=0;dfs2(i);}
  ^~~
oneway.cpp:100:32: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for(int i=0;i<c;i++)vis[i]=0; for(int i=0;i<c;i++)if(!vis[i]){ldep[i]=0;dfs2(i);}
                                ^~~
oneway.cpp:81:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~
oneway.cpp:87:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&a,&b);a--;b--;edge[i]=make_pair(a,b);
   ~~~~~^~~~~~~~~~~~~~
oneway.cpp:102:13: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int p;scanf("%d",&p);
        ~~~~~^~~~~~~~~
oneway.cpp:104:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&q[i].first,&q[i].second);q[i].first--;q[i].second--;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40