oj.uz

Submission #442492

# Submission time Handle Problem Language Result Execution time Memory
442492 2021-07-08T01:39:31 Z nguot One-Way Streets (CEOI17_oneway) C++14
100 / 100
 353 ms 34576 KB 
#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

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 5452 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 5 ms 5580 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5452 KB Output is correct
7 Correct 5 ms 5580 KB Output is correct
8 Correct 5 ms 5580 KB Output is correct
9 Correct 5 ms 5452 KB Output is correct
10 Correct 5 ms 5420 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 5452 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 5 ms 5580 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5452 KB Output is correct
7 Correct 5 ms 5580 KB Output is correct
8 Correct 5 ms 5580 KB Output is correct
9 Correct 5 ms 5452 KB Output is correct
10 Correct 5 ms 5420 KB Output is correct
11 Correct 44 ms 11764 KB Output is correct
12 Correct 54 ms 13280 KB Output is correct
13 Correct 68 ms 14920 KB Output is correct
14 Correct 110 ms 18808 KB Output is correct
15 Correct 96 ms 20408 KB Output is correct
16 Correct 152 ms 27708 KB Output is correct
17 Correct 146 ms 29196 KB Output is correct
18 Correct 142 ms 27912 KB Output is correct
19 Correct 151 ms 30332 KB Output is correct
20 Correct 74 ms 12588 KB Output is correct
21 Correct 53 ms 12740 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5452 KB Output is correct
2 Correct 3 ms 5452 KB Output is correct
3 Correct 4 ms 5452 KB Output is correct
4 Correct 5 ms 5580 KB Output is correct
5 Correct 4 ms 5708 KB Output is correct
6 Correct 3 ms 5452 KB Output is correct
7 Correct 5 ms 5580 KB Output is correct
8 Correct 5 ms 5580 KB Output is correct
9 Correct 5 ms 5452 KB Output is correct
10 Correct 5 ms 5420 KB Output is correct
11 Correct 44 ms 11764 KB Output is correct
12 Correct 54 ms 13280 KB Output is correct
13 Correct 68 ms 14920 KB Output is correct
14 Correct 110 ms 18808 KB Output is correct
15 Correct 96 ms 20408 KB Output is correct
16 Correct 152 ms 27708 KB Output is correct
17 Correct 146 ms 29196 KB Output is correct
18 Correct 142 ms 27912 KB Output is correct
19 Correct 151 ms 30332 KB Output is correct
20 Correct 74 ms 12588 KB Output is correct
21 Correct 53 ms 12740 KB Output is correct
22 Correct 353 ms 31636 KB Output is correct
23 Correct 319 ms 30192 KB Output is correct
24 Correct 256 ms 30332 KB Output is correct
25 Correct 302 ms 34576 KB Output is correct
26 Correct 306 ms 31304 KB Output is correct
27 Correct 304 ms 30260 KB Output is correct
28 Correct 51 ms 11060 KB Output is correct
29 Correct 107 ms 14612 KB Output is correct
30 Correct 111 ms 14952 KB Output is correct
31 Correct 101 ms 15076 KB Output is correct
32 Correct 169 ms 23184 KB Output is correct