oj.uz

Submission #449015

# Submission time Handle Problem Language Result Execution time Memory
449015 2021-08-02T04:14:04 Z ak2006 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 171 ms 25860 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using vc = vector<char>;
using vvc = vector<vc>;
using vs = vector<string>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
}
int n = 1e5 + 5,m,cmp,TIMER;
vvi adj(n),graph(n);
vb ins(n);
vi dfs_time(n),dfs_low(n),num(n),scc(n),dist(n);
stack<int>s;
void dfs(int u,int p)
{
    dfs_low[u] = dfs_time[u] = ++TIMER;
    s.push(u);
    ins[u] = 1;
    for (int v:adj[u]){
        if (v == p){p = -1;continue;}
        if (!dfs_time[v]){
            dfs(v,u);
            dfs_low[u] = min(dfs_low[u],dfs_low[v]);
            continue;
        }
        if (ins[v])
            dfs_low[u] = min(dfs_low[u],dfs_time[v]);
    }
    if (dfs_time[u] == dfs_low[u]){
        int v = -1;
        cmp++;
        while (v != u){
            v = s.top();
            scc[v] = cmp;
            ins[v] = 0;
            s.pop();   
        }
    }
}   
void tree(int u,int p)
{
    for (int v:graph[u]){
        if (v == p)continue;
        dist[v] = dist[u] + 1;
        tree(v,u);
        num[u] += num[v];
    }
    //cout<<u<<" "<<num[u]<<endl;
}
int main()
{
    setIO();
    cin>>n>>m;
    vvi edges;
    while (m--){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v),adj[v].pb(u);
        edges.pb({u,v});
    }
    for (int i = 1;i<=n;i++)
        if (!dfs_time[i])dfs(i,-1);
    int q;
    cin>>q;
    while (q--){
        int u,v;
        cin>>u>>v;
        num[scc[u]]++,num[scc[v]]--;
        //cout<<"HERE "<<scc[u]<<" "<<scc[v]<<" "<<num[scc[u]]<<" "<<num[scc[v]]<<endl;
    }
    for (auto it:edges){
        int u = scc[it[0]],v = scc[it[1]];
        if (u != v)
        graph[u].pb(v),graph[v].pb(u);
    }
    for (int i = 1;i<=cmp;i++)
        if (!dist[i])tree(i,-1);
    
    for (auto it:edges){
        int u = scc[it[0]],v = scc[it[1]];
        if (dist[u] > dist[v])swap(u,v);
        //cout<<u<<" "<<v<<" "<<num[u]<<" "<<num[v]<<endl;
    }
    for (auto it:edges){
        int u = scc[it[0]],v = scc[it[1]];
        if (u == v){cout<<"B";continue;}
        
        if (dist[u] > dist[v]){
            if (num[u] > 0)cout<<"R";
            else if (num[u] == 0)cout<<"B";
            else cout<<"L";
        }
        else{
            if (num[v] > 0)cout<<"L";
            else if (num[v] == 0)cout<<"B";
            else cout<<"R";
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6988 KB Output is correct
2 Correct 5 ms 6988 KB Output is correct
3 Correct 5 ms 6988 KB Output is correct
4 Correct 5 ms 7128 KB Output is correct
5 Correct 5 ms 7116 KB Output is correct
6 Correct 5 ms 7016 KB Output is correct
7 Correct 5 ms 7116 KB Output is correct
8 Correct 5 ms 7116 KB Output is correct
9 Correct 5 ms 6988 KB Output is correct
10 Correct 5 ms 7000 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6988 KB Output is correct
2 Correct 5 ms 6988 KB Output is correct
3 Correct 5 ms 6988 KB Output is correct
4 Correct 5 ms 7128 KB Output is correct
5 Correct 5 ms 7116 KB Output is correct
6 Correct 5 ms 7016 KB Output is correct
7 Correct 5 ms 7116 KB Output is correct
8 Correct 5 ms 7116 KB Output is correct
9 Correct 5 ms 6988 KB Output is correct
10 Correct 5 ms 7000 KB Output is correct
11 Correct 72 ms 16324 KB Output is correct
12 Correct 72 ms 17016 KB Output is correct
13 Correct 92 ms 18076 KB Output is correct
14 Correct 120 ms 19156 KB Output is correct
15 Correct 114 ms 19568 KB Output is correct
16 Correct 149 ms 20080 KB Output is correct
17 Correct 128 ms 21620 KB Output is correct
18 Correct 152 ms 20088 KB Output is correct
19 Correct 101 ms 22788 KB Output is correct
20 Correct 83 ms 17024 KB Output is correct
21 Correct 69 ms 16700 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6988 KB Output is correct
2 Correct 5 ms 6988 KB Output is correct
3 Correct 5 ms 6988 KB Output is correct
4 Correct 5 ms 7128 KB Output is correct
5 Correct 5 ms 7116 KB Output is correct
6 Correct 5 ms 7016 KB Output is correct
7 Correct 5 ms 7116 KB Output is correct
8 Correct 5 ms 7116 KB Output is correct
9 Correct 5 ms 6988 KB Output is correct
10 Correct 5 ms 7000 KB Output is correct
11 Correct 72 ms 16324 KB Output is correct
12 Correct 72 ms 17016 KB Output is correct
13 Correct 92 ms 18076 KB Output is correct
14 Correct 120 ms 19156 KB Output is correct
15 Correct 114 ms 19568 KB Output is correct
16 Correct 149 ms 20080 KB Output is correct
17 Correct 128 ms 21620 KB Output is correct
18 Correct 152 ms 20088 KB Output is correct
19 Correct 101 ms 22788 KB Output is correct
20 Correct 83 ms 17024 KB Output is correct
21 Correct 69 ms 16700 KB Output is correct
22 Correct 119 ms 22792 KB Output is correct
23 Correct 129 ms 21284 KB Output is correct
24 Correct 171 ms 21328 KB Output is correct
25 Correct 117 ms 25860 KB Output is correct
26 Correct 128 ms 22384 KB Output is correct
27 Correct 135 ms 21364 KB Output is correct
28 Correct 64 ms 14564 KB Output is correct
29 Correct 94 ms 17688 KB Output is correct
30 Correct 91 ms 17768 KB Output is correct
31 Correct 109 ms 18192 KB Output is correct
32 Correct 105 ms 20708 KB Output is correct