제출 #199517

#제출 시각아이디문제언어결과실행 시간메모리
199517algorithm16One-Way Streets (CEOI17_oneway)C++14
0 / 100
7 ms3580 KiB
#include<iostream> #include<cmath> #include<vector> #include<map> #include<string> #include<cstring> #include<algorithm> using namespace std; int n,m,p,bio[100005],d[100005],t=1,lo[100005],parent[100005],depth[100005],par2[25][100005],arr[100005],ind[100005]; vector <int> v[100005]; vector <pair<int,int> > v2; vector <pair<int,int> > v3; vector <pair<int,int> > p1; map <pair<int,int>,int> m1; string sol; int find_par(int x) { if(x==parent[x]) return x; int par=find_par(parent[x]); parent[x]=par; return par; } void spoji(int x,int y) { if(x>y) swap(x,y); //cout << x << " " << y << "\n"; x=find_par(x); y=find_par(y); //cout << x << " " << y << "\n"; if(x==y) return; if(depth[x]==depth[y]) depth[x]+=1; if(depth[x]>depth[y]) parent[y]=x; else parent[x]=y; } int dfs(int x,int par) { bio[x]=1; d[x]=t; t+=1; int ret=1e9; for(int i=0;i<v[x].size();i++) { if(v[x][i]==par) continue; if(bio[v[x][i]]) { //sol[abs(m1[make_pair(x,v[x][i])])-1]='B'; ret=min(ret,d[v[x][i]]); spoji(x,v[x][i]); } else { ret=min(ret,dfs(v[x][i],x)); if(d[x]<lo[v[x][i]]) { v3.push_back(make_pair(min(x,v[x][i]),max(x,v[x][i]))); sol[abs(m1[make_pair(x,v[x][i])])-1]=' '; } else { //cout << "abc " << x << " " << v[x][i] << "\n"; spoji(x,v[x][i]); //sol[abs(m1[make_pair(x,v[x][i])])-1]='B'; } } } lo[x]=ret; return ret; } void dfs2(int x,int par,int d1) { par2[0][x]=par; depth[x]=d1; for(int i=0;i<v[x].size();i++) { if(v[x][i]==par) continue; dfs2(v[x][i],x,d1+1); } } int lca(int a,int b) { if(depth[a]<depth[b]) swap(a,b); for(int i=20;i>=0;i--) { if((depth[a]-depth[b]) & (1 << i)) a=par2[i][a]; } if(a==b) return a; for(int i=20;i>=0;i--) { if(par2[i][a]==par2[i][b]) continue; a=par2[i][a]; b=par2[i][b]; } return par2[0][a]; } int dfs3(int x,int par) { int ret=arr[x]; for(int i=0;i<v[x].size();i++) { if(v[x][i]==par) continue; ret+=dfs3(v[x][i],x); } //cout << x << " " << ret << " " << m1[make_pair(x,par)] << "\n"; if(x) { if(ret==0 && sol[abs(m1[make_pair(x,par)])-1]!='L' && sol[abs(m1[make_pair(x,par)])-1]!='R') sol[abs(m1[make_pair(x,par)])-1]='B'; else if(ret==0) return ret; else if(ret<0) { if(m1[make_pair(x,par)]>0) sol[m1[make_pair(x,par)]-1]='R'; else sol[-m1[make_pair(x,par)]-1]='L'; } else { //cout << x << " " << par << " " << ret << " " << m1[make_pair(x,par)] << "\n"; if(m1[make_pair(x,par)]<0) sol[-m1[make_pair(x,par)]-1]='R'; else sol[m1[make_pair(x,par)]-1]='L'; } } return ret; } int main() { cin >> n >> m; v2.clear(); v3.clear(); for(int i=0;i<n;i++) { depth[i]=1; parent[i]=i; } for(int j=0;j<m;j++) { sol+='B'; int a,b; cin >> a >> b; m1[make_pair(a-1,b-1)]=j+1; m1[make_pair(b-1,a-1)]=-j-1; v2.push_back(make_pair(a-1,b-1)); v[a-1].push_back(b-1); v[b-1].push_back(a-1); } cin >> p; for(int i=0;i<p;i++) { int a,b; cin >> a >> b; p1.push_back(make_pair(a-1,b-1)); } dfs(0,-1); /*for(int i=0;i<v3.size();i++) { cout << v3[i].first << " " << v3[i].second << "\n"; }*/ for(int i=0;i<n;i++) { v[i].clear(); } for(int i=0;i<m;i++) { if(find_par(v2[i].first)==find_par(v2[i].second)) continue; v[find_par(v2[i].first)].push_back(find_par(v2[i].second)); v[find_par(v2[i].second)].push_back(find_par(v2[i].first)); m1[make_pair(find_par(v2[i].first),find_par(v2[i].second))]=i+1; m1[make_pair(find_par(v2[i].second),find_par(v2[i].first))]=-i-1; ind[v2[i].first]=find_par(v2[i].first); ind[v2[i].second]=find_par(v2[i].second); } /*for(int i=0;i<n;i++) { cout << ind[i] << " "; } cout << "\n";*/ memset(depth,0,sizeof(depth)); dfs2(0,-1,0); for(int i=1;i<20;i++) { for(int j=0;j<n;j++) { par2[i][j]=par2[i-1][par2[i-1][j]]; } } for(int i=0;i<p;i++) { arr[ind[p1[i].first]]-=1; arr[lca(ind[p1[i].first],ind[p1[i].second])]+=1; //cout << ind[p1[i].first] << " " << ind[p1[i].second] << " " << lca(ind[p1[i].first],ind[p1[i].second]) << "\n"; } dfs3(0,-1); //cout << sol << "\n"; memset(arr,0,sizeof(arr)); for(int i=0;i<p;i++) { arr[ind[p1[i].second]]+=1; arr[lca(ind[p1[i].first],ind[p1[i].second])]-=1; //cout << p1[i].first << " " << p1[i].second << " " << lca(p1[i].first,p1[i].second) << "\n"; } dfs3(0,-1); cout << sol; return 0; }

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

oneway.cpp: In function 'int dfs(int, int)':
oneway.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp: In function 'void dfs2(int, int, int)':
oneway.cpp:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
oneway.cpp: In function 'int dfs3(int, int)':
oneway.cpp:84:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<v[x].size();i++) {
              ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...