oj.uz

Submission #591616

# Submission time Handle Problem Language Result Execution time Memory
591616 2022-07-07T16:59:56 Z VasLemmy One-Way Streets (CEOI17_oneway) C++17
100 / 100
 442 ms 141132 KB 
/// slava sovet·skomu soyuzu
#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define ll long long
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back

const ll mod = 1e9 + 7;
const int maxN = 2000005;

int n,m,p;
int x[maxN],y[maxN];
vector<pii> adj1[maxN];
map<pii,int> apr;
char res[maxN];
int isbridge[maxN];

string juryoutput;

void read()
{
    //cin >> juryoutput;
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        cin >> x[i] >> y[i];
        res[i] = 'B';
        if(x[i] == y[i])
        {
            continue;
        }
        if(apr[make_pair(min(x[i],y[i]),max(x[i],y[i]))] == 0)
        {
            adj1[x[i]].push_back({y[i],i});
            adj1[y[i]].push_back({x[i],i});
        }
        apr[make_pair(min(x[i],y[i]),max(x[i],y[i]))]++;
    }
}

int num[maxN],low[maxN];
int TimeDFS = 0;

void preDFS(int u,int pre)
{
    num[u] = low[u] = ++TimeDFS;
    for(pii x : adj1[u])
    {
        if(x.fi == pre) continue;
        if(!num[x.fi])
        {
            preDFS(x.fi,u);
            low[u] = min(low[u],low[x.fi]);
            if(low[x.fi] == num[x.fi] && apr[ {min(u,x.fi),max(u,x.fi)}] == 1)
            {
                isbridge[x.se] = 1;
            }
        }
        else
        {
            low[u] = min(low[u],num[x.fi]);
        }
    }
}

int isvis[maxN];
int cnt_grp = 0;
vector<vector<int>> adj2[maxN];
int grp[maxN];

/// 1 la phai
/// 0 la trai

void DFS_Build(int u)
{
    isvis[u] = 1;
    for(pii t : adj1[u])
    {
        if(isvis[t.fi]) continue;
        if(isbridge[t.se])
        {
            cnt_grp++;
            grp[t.fi] = cnt_grp;
            if(u == x[t.se])
            {
                adj2[grp[u]].push_back({grp[t.fi],t.se,1});
                adj2[grp[t.fi]].push_back({grp[u],t.se,0});
            }
            else
            {
                adj2[grp[u]].push_back({grp[t.fi],t.se,0});
                adj2[grp[t.fi]].push_back({grp[u],t.se,1});
            }
        }
        else grp[t.fi] = grp[u];
        DFS_Build(t.fi);
    }
}

int save_e[maxN];
int anc[25][maxN];
int dp[maxN];
int ifused[maxN];
int depth[maxN];

void DFS2(int u,int p)
{
    for(vector<int> x : adj2[u])
    {
        int v = x[0];
        if(v == p) continue;
        depth[v] = depth[u] + 1;
        save_e[v] = x[1];
        if(x[2] == 1)
        {
            res[x[1]] = 'R';
        }
        else res[x[1]] = 'L';
        anc[0][v] = u;
        for(int i = 1; i <= (int)log2(n); i++)
        {
            anc[i][v] = anc[i-1][anc[i-1][v]];
        }
        DFS2(v,u);
    }
}

void DFS3(int u,int p)
{
    for(vector<int> x : adj2[u])
    {
        int v = x[0];
        if(v == p) continue;
        DFS3(v,u);
        dp[u] += dp[v];
    }
}

void DFS4(int u,int p)
{
    for(vector<int> x : adj2[u])
    {
        int v = x[0];
        if(v == p) continue;
        DFS4(v,u);
        ifused[u] += ifused[v];
    }
}

int LCA(int u,int v)
{
    if(depth[u] < depth[v]) swap(u,v);
    int k = depth[u] - depth[v];
    for(int i = (int)log2(n); i >= 0; i--)
    {
        if(k & (1 << i))
        {
            u = anc[i][u];
        }
    }
    if(u == v) return u;
    for(int i = (int)log2(n); i >= 0; i--)
    {
        if(anc[i][u] != anc[i][v])
        {
            u = anc[i][u];
            v = anc[i][v];
        }
    }
    return anc[0][u];
}

void sol()
{
    for(int i = 1; i <= n; i++)
    {
        if(!num[i])
        {
            preDFS(i,i);
        }
    }

    for(int i = 1; i <= n; i++)
    {
        if(!isvis[i])
        {
            cnt_grp++;
            grp[i] = cnt_grp;
            DFS_Build(i);
        }
    }
    /*for(int i = 1; i <= n; i++)
    {
        cout << grp[i] <<' ';
    }
    cout <<'\n'<<"dark";
    return;*/

    for(int i = 1; i <= cnt_grp; i++)
    {
        if(depth[i] == 0) DFS2(i,i);
    }
    cin >> p;
    while(p--)
    {
        int a,b;
        cin >> a >> b;
        dp[LCA(grp[a],grp[b])]--;
        dp[grp[a]]++;
        ifused[LCA(grp[a],grp[b])] -= 2;
        ifused[grp[a]]++;
        ifused[grp[b]]++;
    }
    //cout << save_e[2];return;
    for(int i = 1; i <= cnt_grp; i++)
    {
        if(depth[i] == 0)
        {
                DFS3(i,i);
                DFS4(i,i);
        }
    }
    for(int i = 1; i <= cnt_grp; i++)
    {
        if(depth[i] == 0)
        {
            continue;
        }
        if(dp[i] > 0)
        {
            res[save_e[i]] = 'L' + 'R' - res[save_e[i]];
        }
        else if(ifused[i] == 0)
        {
            res[save_e[i]] = 'B';
        }
    }
    string g;
    for(int i = 1; i <= m; i++)
    {
       cout << res[i];
       g.push_back(res[i]);
       //if(res[i] != juryoutput[i-1]) {cout <<"sai o"<<' '<< i <<'\n';}
    }
    //cout << juryoutput <<'\n'<< g <<'\n';
    //if(g == juryoutput) cout <<"OK";
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tests;
    //cin >> tests;
    tests = 1;
    while (tests--)
    {
        read();
        sol();
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94288 KB Output is correct
2 Correct 46 ms 94284 KB Output is correct
3 Correct 57 ms 94524 KB Output is correct
4 Correct 54 ms 94672 KB Output is correct
5 Correct 47 ms 94768 KB Output is correct
6 Correct 45 ms 94400 KB Output is correct
7 Correct 46 ms 94724 KB Output is correct
8 Correct 46 ms 94696 KB Output is correct
9 Correct 46 ms 94508 KB Output is correct
10 Correct 45 ms 94540 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94288 KB Output is correct
2 Correct 46 ms 94284 KB Output is correct
3 Correct 57 ms 94524 KB Output is correct
4 Correct 54 ms 94672 KB Output is correct
5 Correct 47 ms 94768 KB Output is correct
6 Correct 45 ms 94400 KB Output is correct
7 Correct 46 ms 94724 KB Output is correct
8 Correct 46 ms 94696 KB Output is correct
9 Correct 46 ms 94508 KB Output is correct
10 Correct 45 ms 94540 KB Output is correct
11 Correct 137 ms 108236 KB Output is correct
12 Correct 141 ms 110028 KB Output is correct
13 Correct 161 ms 112076 KB Output is correct
14 Correct 192 ms 116912 KB Output is correct
15 Correct 279 ms 118656 KB Output is correct
16 Correct 279 ms 129752 KB Output is correct
17 Correct 298 ms 133172 KB Output is correct
18 Correct 349 ms 129792 KB Output is correct
19 Correct 252 ms 135568 KB Output is correct
20 Correct 148 ms 108884 KB Output is correct
21 Correct 157 ms 108592 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 94288 KB Output is correct
2 Correct 46 ms 94284 KB Output is correct
3 Correct 57 ms 94524 KB Output is correct
4 Correct 54 ms 94672 KB Output is correct
5 Correct 47 ms 94768 KB Output is correct
6 Correct 45 ms 94400 KB Output is correct
7 Correct 46 ms 94724 KB Output is correct
8 Correct 46 ms 94696 KB Output is correct
9 Correct 46 ms 94508 KB Output is correct
10 Correct 45 ms 94540 KB Output is correct
11 Correct 137 ms 108236 KB Output is correct
12 Correct 141 ms 110028 KB Output is correct
13 Correct 161 ms 112076 KB Output is correct
14 Correct 192 ms 116912 KB Output is correct
15 Correct 279 ms 118656 KB Output is correct
16 Correct 279 ms 129752 KB Output is correct
17 Correct 298 ms 133172 KB Output is correct
18 Correct 349 ms 129792 KB Output is correct
19 Correct 252 ms 135568 KB Output is correct
20 Correct 148 ms 108884 KB Output is correct
21 Correct 157 ms 108592 KB Output is correct
22 Correct 442 ms 134240 KB Output is correct
23 Correct 374 ms 130928 KB Output is correct
24 Correct 353 ms 130920 KB Output is correct
25 Correct 306 ms 141132 KB Output is correct
26 Correct 335 ms 133364 KB Output is correct
27 Correct 318 ms 131132 KB Output is correct
28 Correct 93 ms 97116 KB Output is correct
29 Correct 185 ms 109260 KB Output is correct
30 Correct 176 ms 109760 KB Output is correct
31 Correct 168 ms 110124 KB Output is correct
32 Correct 223 ms 118380 KB Output is correct