Submission #631826

#	Time	Username	Problem	Language	Result	Execution time	Memory
631826		NintsiChkhaidze	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	278 ms	31144 KiB

oneway

#include <bits/stdc++.h>
#define s second
#define f first
#define pb push_back
#define left (h<<1),l,((l+r)>>1)
#define right ((h<<1)|1),((l+r)>>1) + 1,r
using namespace std;
 
const int N = 100005;
int tin[N],low[N],a[N],b[N],ID[N],d[25][N];
int O[N],C[N];
bool bridge[N],vis[N];
vector <int> adj[N],vec[N];
vector <pair<int,int> > v[N];
int idx,cnt,n;
 
void dfs(int x,int par){
    vis[x] = 1;
    tin[x] = low[x] = cnt++;
    for (auto [to,id]: v[x]){
        if (to == par) continue;
        if (vis[to]){
            low[x] = min(low[x], tin[to]);
        }else{
            dfs(to,x);
            low[x] = min(low[x], low[to]);
            if (low[to] > tin[x]) bridge[id] = 1;
        }
    }
}
 
void dfs1(int x){
    ID[x] = idx;
    vis[x] = 1;
    for (auto [to,id]: v[x]){
        if (!vis[to] && !bridge[id]) dfs1(to);
        else if (!vis[to] && bridge[id]) vec[idx].pb(to);
    }
}
 
void dfs2(int x,int par){
    vis[x] = 1;
    d[0][x] = par;
    tin[x] = tin[par] + 1;
    for (int to: adj[x])
        if (!vis[to]) dfs2(to,x);
}
 
void dfs3(int x,int par){
    vis[x]=1;
    for (int to: adj[x]) 
        if (to!=par) {
            dfs3(to,x);
            O[x] += O[to];
            C[x] += C[to];
        }
}
int lca(int x,int y){
    if (tin[x] < tin[y]) swap(x,y);
    for (int j = 18; j >= 0; j--)
        if (tin[d[j][x]] >= tin[y]) x = d[j][x];
    if (x == y) return x;
    for (int j = 18; j >=0; j--)
        if(d[j][x] != d[j][y]) x = d[j][x],y = d[j][y];
    return d[0][x];
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int m;
    cin>>n>>m;
    for (int i = 1; i <= m; i++){
        cin>>a[i]>>b[i];
        v[a[i]].pb({b[i],i});
        v[b[i]].pb({a[i],i});
    }
 
    for (int i= 1; i <= n; i++)
        if (!vis[i]) dfs(i,i); 
 
    for (int i = 1; i <= n; i++) {
        sort(v[i].begin(),v[i].end());
        for (int j = 1; j < v[i].size(); j++)
            if (v[i][j].f == v[i][j - 1].f) bridge[v[i][j].s] = bridge[v[i][j - 1].s] = 0;
    }
    
    for (int i= 1; i <= n; i++) 
        vis[i] = 0;

    idx = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i]) idx++,dfs1(i);
    
    for (int i = 1; i <= n; i++)
        for (int x: vec[i])
            adj[i].pb(ID[x]),adj[ID[x]].pb(i);
            
    for (int i = 1; i <= n; i++)
        tin[i] = 0,vis[i] = 0;
    
    cnt=0;
    for (int i = 1; i <= n; i++) 
        if (!vis[i]) dfs2(i,i);
        
    for (int j = 1; j < 19; j++)
        for (int i = 1; i <= n; i++)
            d[j][i] = d[j - 1][d[j - 1][i]];
 
    int k;
    cin>>k;
    for (int i = 1; i <= k; i++){
        int x,y;
        cin>>x>>y;
        x = ID[x],y = ID[y];
        int c = lca(x,y);
        O[x]++; O[c]--;
        C[y]++; C[c]--;
    }
    
    for (int i = 1; i <= n; i++) vis[i] = 0;
    for (int i = 1; i <= n; i++) if (!vis[i]) dfs3(i,i);
    
    for (int i = 1; i <= m; i++){
        if (!bridge[i]) cout<<'B';
        else{
            int x = ID[a[i]],y = ID[b[i]];
            if (tin[x] >= tin[y]){
                if(O[x] && !C[x]) cout<<'R';
                else if (!O[x] && C[x]) cout<<'L';
                else cout<<'B';
            }else{
                if(O[y] && !C[y]) cout<<'L';
                else if (!O[y] && C[y]) cout<<'R';
                else cout<<'B';
            }
        }
    }
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:20:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   20 |     for (auto [to,id]: v[x]){
      |               ^
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:35:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   35 |     for (auto [to,id]: v[x]){
      |               ^
oneway.cpp: In function 'int main()':
oneway.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |         for (int j = 1; j < v[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40