oj.uz

Submission #222329

# Submission time Handle Problem Language Result Execution time Memory
222329 2020-04-13T03:30:25 Z jamielim One-Way Streets (CEOI17_oneway) C++14
0 / 100
 12 ms 13440 KB 
#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];
void dfs(int x,int d){
	vis[x]=1;
	dep[x]=low[x]=d;
	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,d+1);
			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];int 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(scc,-1,sizeof(scc));memset(pa,-1,sizeof(pa));
	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,0);
	//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++){
		a=edge[i].first,b=edge[i].second;
		if(scc[a]==scc[b])continue;
		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])dfs2(i);
	for(int i=1;i<19;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(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);
		dir(scc[a],r[i].first,1);
		dir(scc[b],r[i].first,-1);
	}
	for(int i=0;i<m;i++){
		if(ans[i]==0)printf("B");
		else if(ans[i]==1)printf("R");
		else printf("L");
	}
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:95: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])dfs2(i);
  ^~~
oneway.cpp:95: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])dfs2(i);
                                ^~~
oneway.cpp:79: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:83: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:97: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:99: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
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13312 KB Output is correct
2 Correct 11 ms 13312 KB Output is correct
3 Correct 11 ms 13312 KB Output is correct
4 Correct 12 ms 13440 KB Output is correct
5 Incorrect 12 ms 13440 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13312 KB Output is correct
2 Correct 11 ms 13312 KB Output is correct
3 Correct 11 ms 13312 KB Output is correct
4 Correct 12 ms 13440 KB Output is correct
5 Incorrect 12 ms 13440 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 13312 KB Output is correct
2 Correct 11 ms 13312 KB Output is correct
3 Correct 11 ms 13312 KB Output is correct
4 Correct 12 ms 13440 KB Output is correct
5 Incorrect 12 ms 13440 KB Output isn't correct
6 Halted 0 ms 0 KB -