oj.uz

Submission #1005328

# Submission time Handle Problem Language Result Execution time Memory
1005328 2024-06-22T10:26:18 Z milisav One-Way Streets (CEOI17_oneway) C++14
0 / 100
 1 ms 4188 KB 
#include <bits/stdc++.h>
#define maxn 100005
using namespace std;
int n,m;
vector<pair<int,int> > a[maxn];
int disc[maxn];
int low[maxn];
int ct=1;
int l[maxn];
int r[maxn];
char s[maxn];
void dfs(int u,int p=-1,int pi=-1) {
    disc[u]=low[u]=ct++;
    for(auto vt:a[u]) {
        int v=vt.first;
        int i=vt.second;
        if(disc[v]==0) {
            dfs(v,u,i);
            low[u]=min(low[u],low[v]);
            l[u]+=l[v];
            r[u]+=r[v];
            if(low[v]>disc[u]) {
                if(i>0) {
                    if(l[v]>r[v]) s[i]='L';
                    if(l[v]<r[v]) s[i]='R';
                }
                else {
                    if(l[v]>r[v]) s[-i]='R';
                    if(l[v]<r[v]) s[-i]='L';
                }
            }
        }
        else {
            if(v!=p) low[u]=min(low[u],disc[v]);
        }
    }
}
int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=0;i<m;i++) {
        int u,v;
        cin>>u>>v;
        a[u].push_back({v,i});
        a[v].push_back({u,-i});
        s[i]='B';
    }
    int p;
    cin>>p;
    for(int i=0;i<p;i++) {
        int u,v;
        cin>>u>>v;
        l[u]++;
        r[v]++;
    }
    for(int i=1;i<=n;i++) {
        if(disc[i]==0) dfs(i,-1,-1);
    }
    cout<<s<<endl;
    return 0;
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Incorrect 1 ms 4188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Incorrect 1 ms 4188 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4184 KB Output is correct
2 Correct 1 ms 4184 KB Output is correct
3 Correct 1 ms 4184 KB Output is correct
4 Incorrect 1 ms 4188 KB Output isn't correct
5 Halted 0 ms 0 KB -