oj.uz

Submission #858388

# Submission time Handle Problem Language Result Execution time Memory
858388 2023-10-08T10:30:32 Z Tenis0206 One-Way Streets (CEOI17_oneway) C++11
30 / 100
 3000 ms 16648 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];

void dfs(int nod, int nr = 0)
{
    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])
        {
            dfs(i);
            for(int j=1; j<=n; j++)
            {
                sel[j] = 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 9052 KB Output is correct
3 Correct 4 ms 9308 KB Output is correct
4 Correct 2 ms 9056 KB Output is correct
5 Correct 2 ms 9052 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 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 4 ms 9308 KB Output is correct
4 Correct 2 ms 9056 KB Output is correct
5 Correct 2 ms 9052 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 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 24 ms 14928 KB Output is correct
12 Correct 274 ms 15696 KB Output is correct
13 Execution timed out 3050 ms 16648 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9048 KB Output is correct
2 Correct 2 ms 9052 KB Output is correct
3 Correct 4 ms 9308 KB Output is correct
4 Correct 2 ms 9056 KB Output is correct
5 Correct 2 ms 9052 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 9052 KB Output is correct
9 Correct 2 ms 9052 KB Output is correct
10 Correct 3 ms 9052 KB Output is correct
11 Correct 24 ms 14928 KB Output is correct
12 Correct 274 ms 15696 KB Output is correct
13 Execution timed out 3050 ms 16648 KB Time limit exceeded
14 Halted 0 ms 0 KB -