oj.uz

Submission #944244

# Submission time Handle Problem Language Result Execution time Memory
944244 2024-03-12T12:29:18 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 130 ms 39544 KB 
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
#define fork(a,b) for(int k=a;k<b;k++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define seto(x,i) memset(x,i,sizeof x)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pf first
#define ps second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

const int N=100010;
int n,m,p,a,b,c,scc,dfn[N],low[N],id[N],inx,dist[N],val[N];
bool ins[N];
stack<int> st;
vector<int> gr[N];
unordered_set<int> cgr[N];
pii edge[N];

void tarjan(int v,int p)
{
    dfn[v]=low[v]=++inx;
    ins[v]=true; st.push(v);
    for(auto i:gr[v])
    {
        if(i==p)
        {
            p=-1;
            continue;
        }
        if(!dfn[i])
        {
            tarjan(i,v);
            low[v]=min(low[v],low[i]);
        }
        else if(ins[i])
            low[v]=min(low[v],dfn[i]);
    }
    if(dfn[v]==low[v])
    {
        while(st.top()!=v)
        {
            id[st.top()]=scc;
            ins[st.top()]=0;
            st.pop();
        }
        id[st.top()]=scc;
        ins[st.top()]=0;
        st.pop();
        scc++;
    }
}
void dfs(int v,int p)
{
    for(auto i:cgr[v])
        if(i!=p)
        {
            dist[i]=dist[v]+1;
            dfs(i,v);
            val[v]+=val[i];
        }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    fori(0,m)
    {
        cin>>edge[i].pf>>edge[i].ps;
        gr[edge[i].pf].push_back(edge[i].ps);
        gr[edge[i].ps].push_back(edge[i].pf);
    }
    fori(0,n)
        if(!dfn[i])
            tarjan(i,-1);
    fori(0,m)
        if(id[edge[i].pf]!=id[edge[i].ps])
        {
            cgr[id[edge[i].pf]].insert(id[edge[i].ps]);
            cgr[id[edge[i].ps]].insert(id[edge[i].pf]);
        }
    cin>>p;
    fori(0,p)
    {
        cin>>a>>b;
        val[id[a]]++;
        val[id[b]]--;
    }
    fori(0,scc)
        if(!dist[i])
            dfs(i,-1);
    fori(0,m)
    {
        a=id[edge[i].pf]; b=id[edge[i].ps];
        if(a==b)
            cout<<"B";
        if(dist[a]>dist[b])
        {
            if(val[a]>0)
                cout<<"R";
            if(val[a]==0)
                cout<<"B";
            if(val[a]<0)
                cout<<"L";
        }
        if(dist[a]<dist[b])
        {
            if(val[b]>0)
                cout<<"L";
            if(val[b]==0)
                cout<<"B";
            if(val[b]<0)
                cout<<"R";
        }
    }
    return 0;
}

/*idea
use tarjan to compress strongly connected components
all edges in scc are bidirectional
the new graph is a tree
for each path l-r set all of them in that direction
use tree difference array

*/

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10736 KB Output is correct
11 Correct 26 ms 14940 KB Output is correct
12 Correct 29 ms 16140 KB Output is correct
13 Correct 31 ms 17496 KB Output is correct
14 Correct 43 ms 21328 KB Output is correct
15 Correct 47 ms 22736 KB Output is correct
16 Correct 92 ms 32740 KB Output is correct
17 Correct 98 ms 34720 KB Output is correct
18 Correct 100 ms 32592 KB Output is correct
19 Correct 79 ms 36136 KB Output is correct
20 Correct 28 ms 15704 KB Output is correct
21 Correct 26 ms 15452 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10588 KB Output is correct
2 Correct 2 ms 10588 KB Output is correct
3 Correct 3 ms 10588 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 2 ms 10588 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 2 ms 10588 KB Output is correct
10 Correct 2 ms 10736 KB Output is correct
11 Correct 26 ms 14940 KB Output is correct
12 Correct 29 ms 16140 KB Output is correct
13 Correct 31 ms 17496 KB Output is correct
14 Correct 43 ms 21328 KB Output is correct
15 Correct 47 ms 22736 KB Output is correct
16 Correct 92 ms 32740 KB Output is correct
17 Correct 98 ms 34720 KB Output is correct
18 Correct 100 ms 32592 KB Output is correct
19 Correct 79 ms 36136 KB Output is correct
20 Correct 28 ms 15704 KB Output is correct
21 Correct 26 ms 15452 KB Output is correct
22 Correct 106 ms 35940 KB Output is correct
23 Correct 106 ms 34208 KB Output is correct
24 Correct 130 ms 33856 KB Output is correct
25 Correct 90 ms 39544 KB Output is correct
26 Correct 99 ms 35392 KB Output is correct
27 Correct 98 ms 33872 KB Output is correct
28 Correct 22 ms 13148 KB Output is correct
29 Correct 42 ms 16208 KB Output is correct
30 Correct 39 ms 16368 KB Output is correct
31 Correct 45 ms 17016 KB Output is correct
32 Correct 58 ms 24136 KB Output is correct