Submission #442492

#	Time	Username	Problem	Language	Result	Execution time	Memory
442492		nguot	One-Way Streets (CEOI17_oneway)	C++14	100 / 100	353 ms	34576 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define fori(x,a,b) for(int x=a;x<=b;x++)
#define ford(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#define getbit(x,i) ((x>>i)&1)
#define batbit(x,i) (x|(1ll<<i))
#define tatbit(x,i) (x&~(1<<i))
#define gg exit(0);

const int N = 1e5 + 10;
int n,m,x,y,scc,id[N],dd[N],low[N],num[N],it,bri[N];
vector<ii> ke[N];
ii e[N],pa[N];

void dfs(int u,int pr)
{
    low[u] = num[u] = ++it;
    dd[u] = 1;
    forv(v,ke[u]) if(v.fi!=pr)
    {
        if(!dd[v.fi])
        {
            pa[v.fi] = {u,v.se};
            dfs(v.fi,u);
            low[u] = min(low[u],low[v.fi]);
            if(low[v.fi]>num[u]) bri[v.se] = 1;
        }
        else low[u] = min(low[u],num[v.fi]);
    }
    if(low[u]==num[u]) scc++;
}

void comp(int u,int c)
{
    dd[u] = 1;
    id[u] = c;
    forv(v,ke[u]) if(!dd[v.fi])
    {
        if(!bri[v.se]) comp(v.fi,c);
    }
}
vector<ii> ad[N];
int dep[N],pd[N][25];

void dfs1(int u,int pr)
{
    dd[u] = 1;
    fori(i,1,log2(scc)) pd[u][i] = pd[pd[u][i-1]][i-1];
    forv(v,ad[u]) if(!dd[v.fi])
    {
        pd[v.fi][0] = u;
        pa[v.fi] = {u,v.se};
        dep[v.fi] = dep[u] + 1;
        dfs1(v.fi,u);
    }
}

int lca(int u,int v)
{
    if(dep[u]<dep[v]) swap(u,v);
    int del = dep[u]-dep[v];
    ford(i,log2(scc),0) if(getbit(del,i)) u = pd[u][i];
    if(u==v) return u;
    ford(i,log2(scc),0) if(pd[u][i]!=pd[v][i])
    u = pd[u][i],v = pd[v][i];

    return pd[u][0];
}

char sol[N];
int dir[N];
void direct(int x,int anc,int ok)
{
    if(x==anc) return;
    if(dir[x]==0)
    {
        dir[x] = ok;
        int i = pa[x].se,y = pa[x].fi;
        int a = id[e[i].fi],b = id[e[i].se];
        if(ok==-1)
        {
            if(a==x && b==y) sol[i] = 'R';
            else sol[i] = 'L';
        }
        else
        {
            if(a==y && b==x) sol[i] = 'R';
            else sol[i] = 'L';
        }
        direct(y,anc,ok);
    }
    else if(dir[x]!=ok) return;//TH ko lam dc;
}
main()
{
    //freopen("task.inp","r",stdin);
    //freopen("test.out","w",stdout);
    fasty;
    cin>>n>>m;
    fori(i,1,m)
    {
        cin>>x>>y;
        ke[x].pb({y,i});
        ke[y].pb({x,i});
        e[i] = {x,y};
    }
    fori(i,1,n) if(!dd[i]) dfs(i,0);
    reset(dd,0);
    int c=1;
    fori(i,1,n) if(!dd[i]) comp(i,c),++c;

    fori(i,1,m) if(bri[i])
    {
        int u = e[i].fi,v = e[i].se;
        ad[id[u]].pb({id[v],i});
        ad[id[v]].pb({id[u],i});
    }
    reset(dd,0);
    fori(i,1,n) pa[i] = {0,0};
    fori(i,1,scc) dd[i] = 0;
    fori(i,1,scc) if(!dd[i]) dfs1(i,0);


    vector<pair<int,ii> > ord;
    int p;cin>>p;
    fori(i,1,p)
    {
        cin>>x>>y;
        x = id[x],y = id[y];
        int tmp = dep[lca(x,y)];
        ord.pb({tmp,{x,y}});
    }
    fori(i,1,m) sol[i] = 'B';
    sort(all(ord));//theo solution la de tinh cho nhanh
    forv(i,ord)
    {
        int a = i.se.fi,b = i.se.se,l = lca(a,b);
        direct(a,l,-1);
        direct(b,l,1);
    }
    fori(i,1,m) cout<<sol[i];
}

Compilation message (stderr)

oneway.cpp:106:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  106 | main()
      | ^~~~

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