Submission #1175299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1175299		trandangquang	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	101 ms	31812 KiB

oneway

#include<bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define FORD(i,a,b) for(int i=(a); i>=(b); --i)
#define sz(a) (int)(a).size()
#define all(a) (a).begin(),(a).end()
#define ii pair<int,int>
#define fi first
#define se second
#define eb emplace_back
#define pb push_back
#define ll long long

const int N=1e5+5;

int n,m,p,num[N],low[N],tin[N],tout[N],ans[N],par[N],parid[N],up[N][20],h[N],Time;
ii edge[N];

struct HalfEdge{
    int v,id;
};

struct DSU{
    int par[N];
    int find(int a){
        return par[a]==0?a:par[a]=find(par[a]);
    }
    void unite(int a, int b){
        a=find(a); b=find(b);
        if(a!=b){
            par[b]=a;
        }
    }
} dsu,dsu2;

vector<HalfEdge> adj[N],tree[N];

void dfs(int u, int lid){
    num[u]=low[u]=++Time;
    for(HalfEdge he:adj[u]) if(he.id!=lid){
        if(!num[he.v]){
            dfs(he.v,he.id);
            low[u]=min(low[u],low[he.v]);
            if(low[he.v]<num[he.v]) dsu.unite(u,he.v);
        }
        else{
            low[u]=min(low[u],num[he.v]);
        }
    }
}

void dfsTree(int u, int lid){
    tin[u]=++Time;
    for(HalfEdge he:tree[u]) if(he.id!=lid){
        par[he.v]=u;
        parid[he.v]=he.id;
        up[he.v][0]=u;
        FOR(i,1,17){
            up[he.v][i]=up[up[he.v][i-1]][i-1];
        }
        h[he.v]=h[u]+1;
        dfsTree(he.v,he.id);
    }
    tout[u]=Time;
}

bool chkSub(int r, int u){
    return tin[r]<=tin[u]&&tout[u]<=tout[r];
}
int lca(int u, int v){
    if(h[u]<h[v]) swap(u,v);
    int d=h[u]-h[v];
    FOR(i,0,17) if(d>>i&1) u=up[u][i];
    if(u==v) return u;
    FORD(i,17,0){
        if(up[u][i]!=up[v][i]){
            u=up[u][i];
            v=up[v][i];
        }
    }
    return up[u][0];
}

void solve(){
    cin>>n>>m;
    FOR(i,1,m){
        int a,b; cin>>a>>b;
        edge[i]={a,b};
        adj[a].pb({b,i});
        adj[b].pb({a,i});
    }
    FOR(i,1,n) if(!num[i]) dfs(i,0);
    FOR(u,1,n){
        for(HalfEdge he:adj[u]){
            if(dsu.find(u)!=dsu.find(he.v)){
                tree[dsu.find(u)].pb({dsu.find(he.v),he.id});
            }
        }
    }
    Time=0;
    FOR(i,1,n) if(!tin[i]) dfsTree(i,0);
    memset(ans,-1,sizeof(ans));
    cin>>p;
    FOR(i,1,p){
        int x,y; cin>>x>>y;
        x=dsu.find(x);
        y=dsu.find(y);

        if(x==y) continue;

        int l=lca(x,y);
        while(h[x]>h[l]){
            if(dsu.find(edge[parid[x]].fi)==x){
                ans[parid[x]]=0;
            }
            else{
                ans[parid[x]]=1;
            }
//            x=par[x];
            dsu2.unite(par[x],x);
            x=dsu2.find(par[x]);
        }
        while(h[y]>h[l]){
            if(dsu.find(edge[parid[y]].se)==y){
                ans[parid[y]]=0;
            }
            else{
                ans[parid[y]]=1;
            }
//            y=par[y];
            dsu2.unite(par[y],y);
            y=dsu2.find(par[y]);
        }
    }
    FOR(i,1,m){
        if(ans[i]==0) cout<<'R';
        else if(ans[i]==1) cout<<'L';
        else cout<<'B';
    }
}

int32_t main(){
    #define task "oneway"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        freopen(task".out","w",stdout);
    }
    cin.tie(0)->sync_with_stdio(0);

    int tc=1; //cin>>tc;
    FOR(i,1,tc){
        solve();
    }
}

Compilation message (stderr)

oneway.cpp: In function 'int32_t main()':
oneway.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:147:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |         freopen(task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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