Submission #591616

#	Time	Username	Problem	Language	Result	Execution time	Memory
591616		VasLemmy	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	442 ms	141132 KiB

oneway

/// 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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40