oj.uz

Submission #236816

# Submission time Handle Problem Language Result Execution time Memory
236816 2020-06-03T13:17:30 Z Autoratch One-Way Streets (CEOI17_oneway) C++14
100 / 100
 518 ms 41592 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 1;
const int K = 19;

int n,m,p;
vector<int> adj[N];
map<pair<int,int>,int> mul; 
map<pair<int,int>,pair<int,char> > hsh;
bool visited[N];
int res[N],lv[N],dp[K][N];
int rec[N];
string ans;

void dfs(int u,int p)
{
    if(visited[u]) return;
    visited[u] = true;
    lv[u] = lv[p]+1,dp[0][u] = p;
    for(int v : adj[u]) if(v!=p) dfs(v,u);
}

int lca(int a,int b)
{
    if(lv[a]<lv[b]) swap(a,b);
    for(int i = K-1;i >= 0;i--) if(lv[dp[i][a]]>=lv[b]) a = dp[i][a];
    if(a==b) return a;
    for(int i = K-1;i >= 0;i--) if(dp[i][a]!=dp[i][b]) a = dp[i][a],b = dp[i][b];
    return dp[0][a];
}

void solve(int u,int p)
{
    if(visited[u]){ res[u]++,res[p]++,res[lca(u,p)]-=2; return; }
    visited[u] = true;
    for(int v : adj[u]) if(v!=p) solve(v,u);
}

void sum(int u,int p)
{
    if(visited[u]) return;
    visited[u] = true;
    for(int v : adj[u]) if(v!=p) sum(v,u);
    res[p]+=res[u];
}

void run(int u,int p)
{
    if(visited[u]) return;
    visited[u] = true;
    for(int v : adj[u]) if(v!=p) run(v,u);
    rec[p]+=rec[u];
    if(mul[{min(u,p),max(u,p)}]>1) return;
    if(res[u]) return;
    if(rec[u]>0) ans[hsh[{u,p}].first] = hsh[{u,p}].second;
    else if(rec[u]<0) ans[hsh[{p,u}].first] = hsh[{p,u}].second;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;
    for(int i = 0;i < m;i++)
    {
        int a,b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
        hsh[{a,b}] = {i,'R'};
        hsh[{b,a}] = {i,'L'};
        mul[{min(a,b),max(a,b)}]++;
    }
    for(int i = 1;i <= n;i++) if(!visited[i]) dfs(i,0);
    for(int i = 1;i < K;i++) for(int j = 1;j <= n;j++) dp[i][j] =  dp[i-1][dp[i-1][j]];
    for(int i = 1;i <= n;i++) visited[i] = false;
    for(int i = 1;i <= n;i++) if(!visited[i]) solve(i,0);
    for(int i = 1;i <= n;i++) visited[i] = false;
    for(int i = 1;i <= n;i++) if(!visited[i]) sum(i,0);
    cin >> p;
    while(p--)
    {
        int a,b;
        cin >> a >> b;
        rec[a]++,rec[b]--;
    }
    for(int i = 1;i <= n;i++) visited[i] = false;
    ans.resize(m);
    for(int i = 1;i <= n;i++) run(i,0);
    for(int i = 0;i < m;i++) if(ans[i]!='L' and ans[i]!='R') ans[i] = 'B';
    cout << ans;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 7 ms 3200 KB Output is correct
8 Correct 7 ms 3200 KB Output is correct
9 Correct 7 ms 3072 KB Output is correct
10 Correct 7 ms 3072 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 7 ms 3200 KB Output is correct
8 Correct 7 ms 3200 KB Output is correct
9 Correct 7 ms 3072 KB Output is correct
10 Correct 7 ms 3072 KB Output is correct
11 Correct 409 ms 27640 KB Output is correct
12 Correct 450 ms 29492 KB Output is correct
13 Correct 488 ms 32248 KB Output is correct
14 Correct 492 ms 35628 KB Output is correct
15 Correct 517 ms 36728 KB Output is correct
16 Correct 460 ms 34888 KB Output is correct
17 Correct 417 ms 36728 KB Output is correct
18 Correct 460 ms 34808 KB Output is correct
19 Correct 408 ms 38008 KB Output is correct
20 Correct 387 ms 30744 KB Output is correct
21 Correct 351 ms 29432 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2816 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 8 ms 3072 KB Output is correct
4 Correct 7 ms 3072 KB Output is correct
5 Correct 8 ms 3072 KB Output is correct
6 Correct 7 ms 3072 KB Output is correct
7 Correct 7 ms 3200 KB Output is correct
8 Correct 7 ms 3200 KB Output is correct
9 Correct 7 ms 3072 KB Output is correct
10 Correct 7 ms 3072 KB Output is correct
11 Correct 409 ms 27640 KB Output is correct
12 Correct 450 ms 29492 KB Output is correct
13 Correct 488 ms 32248 KB Output is correct
14 Correct 492 ms 35628 KB Output is correct
15 Correct 517 ms 36728 KB Output is correct
16 Correct 460 ms 34888 KB Output is correct
17 Correct 417 ms 36728 KB Output is correct
18 Correct 460 ms 34808 KB Output is correct
19 Correct 408 ms 38008 KB Output is correct
20 Correct 387 ms 30744 KB Output is correct
21 Correct 351 ms 29432 KB Output is correct
22 Correct 460 ms 37852 KB Output is correct
23 Correct 480 ms 36088 KB Output is correct
24 Correct 518 ms 35960 KB Output is correct
25 Correct 449 ms 41592 KB Output is correct
26 Correct 425 ms 37368 KB Output is correct
27 Correct 459 ms 36156 KB Output is correct
28 Correct 110 ms 6136 KB Output is correct
29 Correct 410 ms 31348 KB Output is correct
30 Correct 376 ms 31480 KB Output is correct
31 Correct 425 ms 32064 KB Output is correct
32 Correct 331 ms 30712 KB Output is correct