Submission #1033157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033157		MarwenElarbi	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3099 ms	10844 KiB

oneway

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
#define ii pair<int,int>
template <class T>
using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int nax=1e5+5;
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
vector<pair<int,int>> edge(nax);
vector<pair<int,int>> adj[nax];
string ans;
int depth[nax];
int parent[nax];
vector<pair<int,int>> tre[nax];
vector<int> low[nax];
vector<int> up[nax];
bool vis[nax];
int dp[nax];
void dfs(int x,int p){
    vis[x]=true;
    for(auto u:adj[x]){
        if (u.se==p) continue;
        if (vis[u.fi]){
            if (depth[u.fi]>depth[x]) continue;
            low[u.fi].pb(x);
            up[x].pb(u.fi);
            continue;
        }
        depth[u.fi]=depth[x]+1;
        tre[x].pb(u);
        tre[u.fi].pb({x,u.se});
        dfs(u.fi,u.se);
    }
    return;
}
void trav(int x,int p){
    dp[x]=up[x].size()-low[x].size();
    for(auto u:tre[x]){
        if (u.fi==p) continue;
        trav(u.fi,x);
        dp[x]+=dp[u.fi];
    }
    //cout <<x<<" "<<up[x].size()<<" "<<low[x].size()<<" "<<dp[x]<<endl;
    if (dp[x]==0){
        parent[x]=x;
    }else parent[x]=p;
}
int find(int x){
    if(x==parent[x]) return x;
    return parent[x]=find(parent[x]);
}
int bj[nax][20];
void compute(int x,int p){
    for (int i = 1; i < 20; ++i)
    {
        bj[x][i]=bj[bj[x][i-1]][i-1];
    }
    for(auto u:tre[x]){
        if(u.fi==p) continue;
        bj[u.fi][0]=x;
        compute(u.fi,x);
    }
    return;
}
int jump(int x,int d){
    for (int i = 19; i >= 0; --i)
    {
        if(d&(1<<i)) x=bj[x][i];
    }
    return x;
}
int lca(int x,int y){
    if(depth[x]<depth[y]) swap(x,y);
    x=jump(x,depth[x]-depth[y]);
    if(x==y) return x;
    for (int i = 19; i <= 0 ;--i)
    {
        if(bj[x][i]!=bj[y][i]){
            x=bj[x][i];
            y=bj[y][i];
        }
    }
    return bj[x][0]; 
}
int main()
{
    optimise;
    int n,m;
    cin>>n>>m;
    for (int i = 0; i < m; ++i)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        edge[i]={x,y};
        adj[x].pb({y,i});
        adj[y].pb({x,i});
        ans.pb('B');
    }
    for (int i = 0; i < n; ++i)
    {
        if(vis[i]) continue;
        dfs(i,-1);
        trav(i,-1);
        compute(i,-1);
    }
    int q;
    cin>>q;
    for (int i = 0; i < q; i++)
    {
        int x,y;
        cin>>x>>y;
        x--;y--;
        x=find(x);
        y=find(y);
        int z=lca(find(x),find(y));
        z=find(z);
        while(find(x)!=z){
            x=find(x);
            for(auto u:adj[x]){
                if(u.fi==bj[x][0]){
                    ans[u.se]=(edge[u.se].fi==u.fi ? 'L' : 'R');
                    parent[x]=u.fi;
                }
            }
        }
        while(find(y)!=z){
            y=find(y);
            for(auto u:adj[y]){
                if(u.fi==bj[y][0]){
                    ans[u.se]=(edge[u.se].fi==u.fi ? 'R' : 'L');
                    parent[y]=u.fi;
                }
            }
        }
    }
    cout <<ans<<endl;
}

        

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