oj.uz

Submission #858389

# Submission time Handle Problem Language Result Execution time Memory
858389 2023-10-08T10:32:02 Z Tenis0206 One-Way Streets (CEOI17_oneway) C++11
60 / 100
 3000 ms 21772 KB 
#include <bits/stdc++.h>

using namespace std;

const int nmax = 1e5;
const int oo = INT_MAX;

int n,m,k;

pair<int,int> e[nmax + 5];
vector<pair<int,int>> G[nmax + 5];

bool sel[nmax + 5];

int lvl[nmax + 5], r[nmax + 5];

int p[nmax + 5], u[nmax + 5];

vector<pair<int,int>> rst;

vector<int> out[nmax + 5], in[nmax + 5];

int cnt = 0;

char rez[nmax + 5];

vector<int> l_sel;

void dfs(int nod, int nr = 0)
{
    l_sel.push_back(nod);
    p[nod] = (++cnt);
    sel[nod] = true;
    r[nod] = lvl[nod];
    for(auto it : G[nod])
    {
        if(sel[it.first])
        {
            if(it.second!=nr)
            {
                r[nod] = min(r[nod], lvl[it.first]);
            }
            continue;
        }
        lvl[it.first] = 1 + lvl[nod];
        dfs(it.first,it.second);
        r[nod] = min(r[nod], r[it.first]);
    }
    u[nod] = cnt;
}

void solve(int nod, int nr = 0)
{
    sel[nod] = true;
    for(auto it : G[nod])
    {
        if(sel[it.first])
        {
            if(it.second!=nr)
            {
                rez[it.second] = 'B';
            }
            continue;
        }
        solve(it.first,it.second);
    }
    if(!nr)
    {
        return;
    }
    if(r[nod] < lvl[nod])
    {
        rez[nr] = 'B';
        return;
    }
    bool sus = false, jos = false;
    for(auto it : rst)
    {
        int x = it.first;
        int y = it.second;
        if((p[x] < p[nod] || p[x] > u[nod]) && (p[y] >= p[nod] && p[y] <= u[nod]))
        {
            jos = true;
        }
        if((p[y] < p[nod] || p[y] > u[nod]) && (p[x] >= p[nod] && p[x] <= u[nod]))
        {
            sus = true;
        }
    }
    if(jos)
    {
        if(e[nr].second == nod)
        {
            rez[nr] = 'R';
        }
        else
        {
            rez[nr] = 'L';
        }
    }
    if(sus)
    {
        if(e[nr].second == nod)
        {
            rez[nr] = 'L';
        }
        else
        {
            rez[nr] = 'R';
        }
    }
    if(!sus && !jos)
    {
        rez[nr] = 'B';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
#ifdef home
    freopen("nr.in","r",stdin);
    freopen("nr.out","w",stdout);
#endif // home
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int x,y;
        cin>>x>>y;
        e[i] = {x,y};
        if(x==y)
        {
            rez[i] = 'B';
            continue;
        }
        G[x].push_back({y,i});
        G[y].push_back({x,i});
    }
    cin>>k;
    for(int i=1; i<=k; i++)
    {
        int x,y;
        cin>>x>>y;
        out[x].push_back(y);
        in[y].push_back(x);
        rst.push_back({x,y});
    }
    for(int i=1; i<=n; i++)
    {
        if(!sel[i])
        {
            l_sel.clear();
            dfs(i);
            for(auto it : l_sel)
            {
                sel[it] = false;
            }
            solve(i);
        }
    }
    cout<<rez+1<<'\n';
    return 0;
}

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9048 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9048 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 25 ms 14180 KB Output is correct
12 Correct 30 ms 14940 KB Output is correct
13 Correct 32 ms 15696 KB Output is correct
14 Correct 39 ms 17360 KB Output is correct
15 Correct 40 ms 17364 KB Output is correct
16 Correct 30 ms 15524 KB Output is correct
17 Correct 57 ms 17016 KB Output is correct
18 Correct 78 ms 15564 KB Output is correct
19 Correct 47 ms 18120 KB Output is correct
20 Correct 33 ms 15580 KB Output is correct
21 Correct 30 ms 15296 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9048 KB Output is correct
3 Correct 2 ms 9052 KB Output is correct
4 Correct 2 ms 9052 KB Output is correct
5 Correct 2 ms 9048 KB Output is correct
6 Correct 2 ms 9052 KB Output is correct
7 Correct 2 ms 9052 KB Output is correct
8 Correct 2 ms 9048 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 2 ms 9052 KB Output is correct
11 Correct 25 ms 14180 KB Output is correct
12 Correct 30 ms 14940 KB Output is correct
13 Correct 32 ms 15696 KB Output is correct
14 Correct 39 ms 17360 KB Output is correct
15 Correct 40 ms 17364 KB Output is correct
16 Correct 30 ms 15524 KB Output is correct
17 Correct 57 ms 17016 KB Output is correct
18 Correct 78 ms 15564 KB Output is correct
19 Correct 47 ms 18120 KB Output is correct
20 Correct 33 ms 15580 KB Output is correct
21 Correct 30 ms 15296 KB Output is correct
22 Execution timed out 3031 ms 21772 KB Time limit exceeded
23 Halted 0 ms 0 KB -