제출 #585283

#제출 시각아이디문제언어결과실행 시간메모리
585283krit3379One-Way Streets (CEOI17_oneway)C++17
100 / 100
176 ms22196 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #define N 100005 struct A{ int a,flag,id; }; int dp[N]; vector<A> g[N]; bitset<N> vis,cycle,both,res; map<pair<int,int>,int> mp; pair<int,int> edge[N]; void dfs(int s,int f){ vis[s]=true; for(auto [x,flag,id]:g[s]){ if(x==f)continue; if(vis[x]&&!cycle[id])cycle[id]=true,dp[s]++,dp[x]--; else if(!vis[x])dfs(x,s); } } void sol1(int s,int f){ vis[s]=true; for(auto [x,flag,id]:g[s]){ if(x==f||vis[x])continue; sol1(x,s); if(dp[x])cycle[id]=true; dp[s]+=dp[x]; } } void sol2(int s,int f){ vis[s]=true; for(auto [x,flag,id]:g[s]){ if(x==f||vis[x])continue; sol2(x,s); if(dp[x]){ bool f=dp[x]>0?true:false; res[id]=f^flag; } else both[id]=true; dp[s]+=dp[x]; } } int main(){ int n,m,p,i,a,b; scanf("%d %d",&n,&m); for(i=1;i<=m;i++){ scanf("%d %d",&a,&b); if(!mp.count(minmax(a,b))){ g[a].push_back({b,0,i}); g[b].push_back({a,1,i}); } mp[minmax(a,b)]++; edge[i]={a,b}; } for(i=1;i<=n;i++)if(!vis[i])dfs(i,0); vis=0; for(i=1;i<=n;i++)if(!vis[i])sol1(i,0); vis=0; for(i=1;i<=n;i++)dp[i]=0; scanf("%d",&p); while(p--){ scanf("%d %d",&a,&b); dp[a]++,dp[b]--; } vis=0; for(i=1;i<=n;i++)if(!vis[i])sol2(i,0); for(i=1;i<=m;i++){ if(cycle[i]||both[i]||mp[minmax(edge[i].first,edge[i].second)]>1)printf("B"); else if(res[i])printf("L"); else printf("R"); } return 0; }

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

oneway.cpp: In function 'int main()':
oneway.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |     scanf("%d %d",&n,&m);
      |     ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
oneway.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf("%d",&p);
      |     ~~~~~^~~~~~~~~
oneway.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |         scanf("%d %d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...