Submission #1248280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1248280		Jovica	One-Way Streets (CEOI17_oneway)	C++20	100 / 100	411 ms	96676 KiB

oneway

#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5+1;
vector<vector<int> > adj(maxn);

priority_queue<array<int,2> > pq;
int depth[maxn];
int sparse[maxn][20];
bool visited[maxn+1];

void dfs(int p)
{
    visited[p] = true;
    pq.push({depth[p],p});
    for (auto s: adj[p]){
        if(depth[s] > 0) continue;
        depth[s] = depth[p]+1;
        sparse[s][0] = p;
        dfs(s);
    }
}

map<array<int,2>, bool> most;
map<array<int,2>, int> spomnat_pati;

int LCA(int a,int b)
{
    if (depth[a] < depth[b]) swap(a,b);
    for (int j=19;j>=0;j--)
        if (depth[sparse[a][j]]>=depth[b]) a = sparse[a][j];
    if (a == b) return a;
    for (int j=19;j>=0;j--)
        if (sparse[a][j] != sparse[b][j]) a = sparse[a][j],b = sparse[b][j];

    a = sparse[a][0];
    return a;
}

int low[maxn];
void najdi(int n)
{
    for (int i=1;i<=n;i++) low[i] = i;

    while (pq.size())
    {
        int p = pq.top()[1];pq.pop();

        for (auto s: adj[p])
        {
            if (sparse[p][0] == s) continue;
            if (sparse[s][0] == p) continue;

            int lca = LCA(p,s);
            if (depth[lca] < depth[low[p]]) low[p] = lca;
        }

        if (depth[low[p]] > depth[sparse[p][0]]){
            most[{p,sparse[p][0]}] = most[{sparse[p][0],p}] = true;
        }
        else{
            low[sparse[p][0]] = low[p];
        }
    }
}

int gazda[maxn];
void dsu(int n)
{
    memset(visited,0,sizeof(visited));
    for (int i=1;i<=n;i++)
    {
        if (visited[i]) continue;
        queue<int> q;
        q.push(i);visited[i] = true;
        vector<int> z;
        int m = maxn;
        while (q.size())
        {
            int p = q.front();q.pop();m = min(m,p);

            z.push_back(p);
            for (auto s: adj[p]) if (visited[s] == false && most[{p,s}] == false) visited[s] = true,q.push(s);
        }

        for (auto a: z) gazda[a] = m;
    }

    //for (int i=1;i<=n;i++) cout<<gazda[i]<<" ";cout<<endl;
}

map<array<int,2>,bool > orientiran;

int z = 0;
int niza[maxn];
void dfs1(int x)
{
    vector<int> sosedi;
    queue<int> q;q.push(x);visited[x] = true;
    while (q.size())
    {
        int p = q.front();q.pop();
        for (auto s: adj[p]){
            if (visited[s]) continue;
            if (gazda[p] != gazda[s]) sosedi.push_back(gazda[s]);
            else
            {
                q.push(s);
                visited[s] = true;
            }
        }
    }

    for (auto s: sosedi)
    {
        //cout<<"ulava s = "<<s<<endl;
        if (visited[s]) continue;
        int pret = z;
        dfs1(s);
        int k = pret - z;
        //cout<<"pret = "<<pret<<" z = "<<z<<" k = "<<k<<" gleda do "<<s<<endl;
        if (k == 0) continue;
        if (k > 0) orientiran[{x,s}] = true;
        if (k < 0) orientiran[{s,x}] = true;

    }
    z += niza[x];
}

int main()
{
    int n,m;
    cin>>n>>m;
    vector<array<int,2> > rebra;
    for (int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        rebra.push_back({a,b});
        spomnat_pati[{a,b}]++;spomnat_pati[{b,a}]++;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    depth[1] = 1;
    for (int i=1;i<=n;i++) if (visited[i] == false) dfs(i);
    memset(visited,0,sizeof(visited));

    for (int j=1;j<20;j++)
        for (int i=1;i<=n;i++)
            sparse[i][j] = sparse[sparse[i][j-1]][j-1];

    najdi(n);

    for (auto a: rebra) if (spomnat_pati[a] > 1) most[a] = most[{a[1],a[0]}] = false;
    //for (int i=0;i<rebra.size();i++) if (most[rebra[i]] && spomnat_pati[rebra[i]] == 1) cout<<"M "<<" "<<rebra[i][0]<<" "<<rebra[i][1]<<endl;else cout<<"NM\n";

    dsu(n);

    int q;
    cin>>q;
    for (int i=0;i<q;i++)
    {
        int a,b;
        cin>>a>>b;
        niza[gazda[a]]++;
        niza[gazda[b]]--;
    }

    memset(visited,0,sizeof(visited));
    for (int i=1;i<=n;i++) if (visited[gazda[i]] == false) dfs1(gazda[i]);

    for (auto a: rebra)
    {
        if (orientiran[{gazda[a[0]],gazda[a[1]]}]) cout<<'R';
        else if (orientiran[{gazda[a[1]],gazda[a[0]]}]) cout<<'L';
        else cout<<'B';
    }
    return 0;
}

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40