Submission #908667

#TimeUsernameProblemLanguageResultExecution timeMemory
908667asdasdqwerOne-Way Streets (CEOI17_oneway)C++14
30 / 100
52 ms20164 KiB
#include <bits/stdc++.h> using namespace std; signed main() { ios::sync_with_stdio(false); cin.tie(0); int n,m;cin>>n>>m; vector<vector<int>> g(n); vector<array<int,2>> edg; for (int i=0;i<m;i++) { int a,b;cin>>a>>b;a--;b--; edg.push_back({a,b}); if (a==b) continue; g[a].push_back(b); g[b].push_back(a); } // calculate two-edge connected components vector<int> low(n, 1e9), num(n, 0); vector<vector<int>> cmp; int timer=0; stack<int> st; function<void(int,int)> dfs=[&](int node, int parent) { low[node]=num[node]=++timer; st.push(node); bool multiple = false; for (int x:g[node]) { if (x == parent && !multiple) { multiple = true; continue; } if (num[x] == 0) { dfs(x,node); low[node]=min(low[node],low[x]); } else { low[node]=min(low[node],num[x]); } } if (low[node] == num[node]) { cmp.push_back({}); while (st.top() != node) { cmp[cmp.size()-1].push_back(st.top()); st.pop(); } cmp[cmp.size()-1].push_back(node); st.pop(); } }; for (int i=0;i<n;i++) { if (num[i]==0) dfs(i,-1); } vector<int> idx(n, -1); for (int i=0;i<cmp.size();i++) { for (int x:cmp[i]) { idx[x]=i; } } vector<vector<int>> tree(cmp.size()); for (int i=0;i<n;i++) { for (int x:g[i]) { if (idx[x] != idx[i]) { tree[idx[i]].push_back(idx[x]); } } } n=cmp.size(); vector<int> p(n,-1), d(n,0); function<void(int,int)> dfs2=[&](int node, int parent) { for (int x:tree[node]) { if (x==parent)continue; else if (p[x] != -1) continue; p[x]=node; d[x]=d[node]+1; dfs2(x,node); } }; for (int i=0;i<n;i++) { if (p[i]==-1)dfs2(i,-1); } vector<vector<int>> lft(n, vector<int>(20)); for (int i=0;i<n;i++) { lft[i][0]=p[i]; } for (int j=1;j<20;j++) { for (int i=0;i<n;i++) { lft[i][j]=lft[i][j-1]; if (lft[i][j] != -1) { lft[i][j]=lft[lft[i][j]][j-1]; } } } function<int(int,int)> jmp=[&](int a, int steps)->int{ int cnt=0; while (steps) { if ((steps&1)==1) { a=lft[a][cnt]; if (a==-1)return -1; } steps>>=1; cnt++; } return a; }; function<int(int,int)> lca=[&](int a, int b) -> int { if (d[a]<d[b])swap(a,b); a=jmp(a,d[a]-d[b]); if (a==b)return a; for (int i=19;i>=0;i--) { if (lft[a][i] != lft[b][i]) { a=lft[a][i]; b=lft[b][i]; } } return lft[a][0]; }; int t;cin>>t; vector<int> up(n, 0), down(n, 0); for (int i=0;i<t;i++) { int a,b;cin>>a>>b;a--;b--; a=idx[a];b=idx[b]; if (a==b)continue; int l=lca(a,b); if (l == a) { down[b]++; down[a]--; } else if (l == b) { up[b]--; up[a]++; } else { up[a]++; down[b]++; up[l]--; down[l]--; } } function<void(int,int)> dfs3=[&](int node, int pv) { for (int x:tree[node]) { if (x==pv)continue; dfs3(x,node); } for (int x:tree[node]) { if (x==pv)continue; up[node]+=up[x]; down[node]+=down[x]; } }; dfs3(0, -1); for (auto x:edg) { x[0]=idx[x[0]]; x[1]=idx[x[1]]; if (x[0]==x[1]) { cout<<"B"; continue; } else if (d[x[0]] < d[x[1]]) { if (up[x[1]] == 0 && down[x[1]] == 0) { cout<<"B"; } else if (up[x[1]] > down[x[1]]) { cout<<"L"; } else { cout<<"R"; } } else { if (up[x[0]] == 0 && down[x[0]] == 0) { cout<<"B"; } else if (up[x[0]] > down[x[0]]) { cout<<"R"; } else { cout<<"L"; } } } cout<<"\n"; }

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:64:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i=0;i<cmp.size();i++) {
      |                  ~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...