oj.uz

답안 #442490

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
442490 2021-07-08T00:57:43 Z nguot One-Way Streets (CEOI17_oneway) C++14
0 / 100
 4 ms 5680 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;
stack<int> s;
vector<int> ke[N];

void dfs(int u,int pr)
{
    low[u] = num[u] = ++it;
    dd[u] = 1;
    s.push(u);
    forv(v,ke[u]) if(v!=pr)
    {
        if(!dd[v])
        {
            dfs(v,u);
            low[u] = min(low[u],low[v]);
        }
        else if(dd[v]==1) low[u] = min(low[u],num[v]);
    }
    if(low[u]==num[u])
    {
        scc++;
        int v;
        do
        {
            v = s.top();s.pop();
            dd[v] = 2;
            id[v] = scc;
        }while(u!=v);
    }
}

vector<ii> ad[N];
int dep[N],pd[N][25];
ii e[N],pa[N];

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),ke[y].pb(x);
        e[i] = {x,y};
    }
    fori(i,1,n) if(!dd[i]) dfs(i,0);
    fori(i,1,m)
    {
        int u = e[i].fi,v = e[i].se;
        if(id[u]!=id[v]) ad[id[u]].pb({id[v],i}),ad[id[v]].pb({id[u],i});
    }
    reset(dd,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:107:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  107 | main()
      | ^~~~

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5324 KB Output is correct
3 Correct 3 ms 5452 KB Output is correct
4 Correct 4 ms 5584 KB Output is correct
5 Correct 4 ms 5628 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5680 KB Output is correct
8 Correct 4 ms 5580 KB Output is correct
9 Incorrect 4 ms 5452 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5324 KB Output is correct
3 Correct 3 ms 5452 KB Output is correct
4 Correct 4 ms 5584 KB Output is correct
5 Correct 4 ms 5628 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5680 KB Output is correct
8 Correct 4 ms 5580 KB Output is correct
9 Incorrect 4 ms 5452 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 3 ms 5324 KB Output is correct
3 Correct 3 ms 5452 KB Output is correct
4 Correct 4 ms 5584 KB Output is correct
5 Correct 4 ms 5628 KB Output is correct
6 Correct 4 ms 5452 KB Output is correct
7 Correct 4 ms 5680 KB Output is correct
8 Correct 4 ms 5580 KB Output is correct
9 Incorrect 4 ms 5452 KB Output isn't correct
10 Halted 0 ms 0 KB -