Submission #811916

#	Time	Username	Problem	Language	Result	Execution time	Memory
811916		Cookie	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	131 ms	33904 KiB

oneway

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const ll mod = 1e9 + 7, inf = 1e9, mxv = 1005, mxn = 2e5 + 5;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n, m, p;
int num[mxn + 1], low[mxn + 1], tt = 0, comp = 0, idcomp[mxn + 1], dep[mxn + 1];
int toedge[mxn + 1], pup[mxn + 1], pdown[mxn + 1], up[mxn + 1][17], ans[mxn + 1];
bool vis[mxn + 1], bridge[mxn + 1];
vt<pii>adj[mxn + 1], g[mxn + 1];
void dfs(int s, int pre){
    low[s] = num[s] = ++tt;
    for(int i = 0; i < sz(adj[s]); i++){
        int v = adj[s][i].first, id = adj[s][i].second;
        if(id % m == pre % m)continue;
        if(!num[v]){
            dfs(v, id);
            low[s] = min(low[s], low[v]);
            if(low[v] > num[s]){
                bridge[id] = 1;
                if(id < m)bridge[id + m] = 1;
                else bridge[id - m] = 1;
            }
        }else low[s] = min(low[s], num[v]);
    }
}
void dfs2(int s){
    idcomp[s] = comp; vis[s] = 1;
    for(int i = 0; i < sz(adj[s]); i++){
        int v = adj[s][i].first, id = adj[s][i].second;
        if(!bridge[id] && !vis[v]){
            dfs2(v);
        }
    }
}
void dfs3(int s, int pre){
   
    vis[s] = 1;
    for(int i = 0; i < sz(g[s]); i++){
        int v = g[s][i].first, id = g[s][i].second;
        if(v == pre)continue;
        dep[v] = dep[s] + 1;
        up[v][0] = s; toedge[v] = id;
        dfs3(v, s);
    }
}
int lca(int u, int v){
    if(dep[u] < dep[v])swap(u, v);
    int k = dep[u] - dep[v];
    for(int i = 0; i < 17; i++){
        if(k & (1 << i)){
            u = up[u][i];
        }
    }
    if(u == v)return(u);
    for(int i = 16; i >= 0; i--){
        if(up[u][i] != up[v][i]){
            u = up[u][i]; v = up[v][i];
        }
    }
    return(up[u][0]);
}
void dfs4(int s, int pre){
    for(int i = 0; i < sz(g[s]); i++){
        int v = g[s][i].first, id = g[s][i].second;
        if(v == pre)continue;
        assert(dep[v] == dep[s] + 1);
        dfs4(v, s);
        pup[s] += pup[v]; pdown[s] += pdown[v];
    }
}
signed main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u, v; cin >> u >> v;
        adj[u].pb(make_pair(v, i));  adj[v].pb(make_pair(u, i + m));
    }
    for(int i = 1; i <= n; i++){
        if(!num[i]){
            dfs(i, -1);
        }
    }
    
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            comp++;
            dfs2(i);
        }
    }
   
    for(int i = 1; i <= n; i++){
        for(int j = 0; j < sz(adj[i]); j++){
            int v = adj[i][j].first, id = adj[i][j].second;
            if(idcomp[i] != idcomp[v]){
              
                g[idcomp[i]].pb(make_pair(idcomp[v], id));
            }
        }
    }
    for(int i = 1; i <= comp; i++){
        vis[i] = 0; toedge[i] = -1;
        sort(g[i].begin(), g[i].end());
        g[i].resize(unique(g[i].begin(), g[i].end()) - g[i].begin());
    }
   
    vt<int>root;
    for(int i = 1; i <= comp; i++){
        if(!vis[i]){
            root.pb(i);
            dfs3(i, -1);
        }
    }
    
    for(int i = 1; i < 17; i++){
        for(int j = 1; j <= comp; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    cin >> p;
    for(int i = 0; i < p; i++){
        int u, v; cin >> u >> v;
        u = idcomp[u]; v = idcomp[v];
        if(u == v)continue;
        int l = lca(u, v);
        //cout << u << " " << v << " " << l << "\n";
        pup[u]++; pdown[v]++; pup[l]--; pdown[l]--;
    }
    for(int i = 0; i < sz(root); i++){
        assert(dep[root[i]] == 0);
        dfs4(root[i], -1);
    }
    
    for(int i = 1; i <= comp; i++){
        //cout << pup[i] << " ";
        
        if(pup[i]){
            assert(!pdown[i]);
            ans[toedge[i] % m] = 1 + ((toedge[i] / m) ^ 1);
        }else if(pdown[i]){
            ans[toedge[i] % m] = 1 + (toedge[i] / m);
        }
    }
    for(int i = 0; i < m; i++){
        if(ans[i] == 0)cout << 'B';
        else if(ans[i] == 1)cout << 'R';
        else cout << 'L';

    }
    
    return(0);
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs4(int, int)':
oneway.cpp:81:32: warning: unused variable 'id' [-Wunused-variable]
   81 |         int v = g[s][i].first, id = g[s][i].second;
      |                                ^~

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