제출 #824990

#제출 시각아이디문제언어결과실행 시간메모리
824990jamezzzOne-Way Streets (CEOI17_oneway)C++17
0 / 100
5 ms13268 KiB
#include <bits/stdc++.h> using namespace std; #ifdef DEBUG #define dbg(...) printf(__VA_ARGS__); #define getchar_unlocked getchar #else #define dbg(...) #endif #define sf scanf #define pf printf #define fi first #define se second #define pb push_back #define psf push_front #define ppb pop_back #define ppf pop_front #define sz(x) (int)x.size() #define mnto(x,y) x=min(x,(__typeof__(x))y) #define mxto(x,y) x=max(x,(__typeof__(x))y) #define INF 1023456789 #define LINF 1023456789123456789 #define all(x) x.begin(),x.end() #define lb(x,v) (lower_bound(all(x),v)-x.begin()) #define ub(x,v) (upper_bound(all(x),v)-x.begin()) #define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin()); typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef pair<ll,ll> pll; typedef tuple<int,int,int> iii; typedef tuple<int,int,int,int> iiii; typedef vector<int> vi; typedef vector<ll> vll; typedef vector<ii> vii; mt19937 rng(time(0)); #define mod 1000000007 inline int add(int a,int b){ int r=a+b; while(r>=mod)r-=mod; while(r<0)r+=mod; return r; } inline int mult(int a,int b){ return (int)(((ll)(a*b))%mod); } inline int rd(){ int x=0; char ch=getchar_unlocked(); while(!(ch&16))ch=getchar_unlocked();//keep reading while current character is whitespace while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered x=(x<<3)+(x<<1)+(ch&15); ch=getchar_unlocked(); } return x; } #define maxn 100005 int n,m,a[maxn],b[maxn],q,x[maxn],y[maxn]; int num[maxn],par[maxn],low[maxn],cnt,bridge[maxn]; int upar[maxn],bcnt,bcc[maxn]; int p[20][maxn],vis[maxn],dep[maxn]; ii to[maxn]; char ans[maxn]; stack<int> s; vector<ii> AL[maxn],AL2[maxn]; void dfs(int u){ num[u]=low[u]=cnt++; s.push(u); for(auto[v,i]:AL[u]){ if(num[v]==-1){ par[v]=u; dfs(v); low[u]=min(low[u],low[v]); if(low[v]>num[u]){ bridge[i]=true; } } else if(v!=par[u]){ low[u]=min(low[u],num[v]); } } } int fp(int i){ return upar[i]==i?i:upar[i]=fp(upar[i]); } void join(int x,int y){ upar[fp(x)]=fp(y); } void dfs2(int u){ vis[u]=true; for(int k=1;k<20;++k){ if(p[k-1][u]!=-1){ p[k][u]=p[k-1][p[k-1][u]]; } } for(auto[v,i]:AL2[u]){ if(p[0][u]==v)continue; p[0][v]=u; dep[v]=dep[u]+1; dfs2(v); } } int lca(int a,int b){ if(dep[a]>dep[b])swap(a,b); for(int k=19;k>=0;--k){ if(p[k][a]!=-1&&dep[p[k][a]]>=dep[b])a=p[k][a]; } if(a==b)return a; for(int k=19;k>=0;--k){ if(p[k][a]!=p[k][b])a=p[k][a],b=p[k][b]; } return p[0][a]; } //returns dep to, dir ii dfs3(int u){ ii res=to[u]; for(auto[v,i]:AL2[u]){ if(p[0][u]==v)continue; ii pr=dfs3(v); if(pr.fi<=dep[u]){ if(pr.se==0){//up if(bcc[a[i]]==v)ans[i]='R'; else ans[i]='L'; } else{//down if(bcc[a[i]]==u)ans[i]='R'; else ans[i]='L'; } } else ans[i]='B'; res=min(res,pr); } return res; } int main(){ sf("%d%d",&n,&m); for(int i=0;i<m;++i){ sf("%d%d",&a[i],&b[i]); AL[a[i]].pb({b[i],i}); AL[b[i]].pb({a[i],i}); } sf("%d",&q); for(int i=0;i<q;++i){ sf("%d%d",&x[i],&y[i]); } memset(num,-1,sizeof num); for(int i=1;i<=n;++i){ if(num[i]==-1){ dfs(i); if(sz(AL[i])==1){ bridge[AL[i][0].se]=true; } } upar[i]=i; } for(int i=0;i<m;++i){ if(!bridge[i]){ join(a[i],b[i]); } } for(int i=1;i<=n;++i){ if(fp(i)==i)bcc[i]=bcnt++; } for(int i=1;i<=n;++i){ bcc[i]=bcc[fp(i)]; } for(int i=0;i<m;++i){ if(bcc[a[i]]==bcc[b[i]]){ ans[i]='B'; } else{ int u=bcc[a[i]],v=bcc[b[i]]; AL2[u].pb({v,i}); AL2[v].pb({u,i}); } } memset(p,-1,sizeof p); for(int i=0;i<bcnt;++i){ if(!vis[i])dfs2(i); to[i]={dep[i],2}; } for(int i=0;i<q;++i){ int u=bcc[x[i]],v=bcc[y[i]]; int l=lca(u,v); if(u!=l){ to[u]=min(to[u],{dep[l],0});//up } if(v!=l){ to[v]=min(to[v],{dep[l],1});//down } } for(int i=0;i<bcnt;++i){ if(p[0][i]==-1)dfs3(i); } for(int i=0;i<m;++i)pf("%c",ans[i]); pf("\n"); } /* 5 6 1 2 1 2 4 3 2 3 1 3 5 1 2 4 5 1 3 */

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

oneway.cpp: In function 'int main()':
oneway.cpp:149:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |  sf("%d%d",&n,&m);
      |    ^
oneway.cpp:151:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  151 |   sf("%d%d",&a[i],&b[i]);
      |     ^
oneway.cpp:155:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  155 |  sf("%d",&q);
      |    ^
oneway.cpp:157:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |   sf("%d%d",&x[i],&y[i]);
      |     ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...