oj.uz

Submission #1027233

# Submission time Handle Problem Language Result Execution time Memory
1027233 2024-07-19T02:26:32 Z ojnewbie111 One-Way Streets (CEOI17_oneway) C++14
0 / 100
 2 ms 3164 KB 
#include<bits/stdc++.h>
#define pi pair<int,int>
#define fi first
#define se second
using namespace std;
const int N=1e5+5;
int n,m,p;
struct node{
    int to,num,direct;
};
vector<node>g[N];
vector<pi>edge;
bool vis[N];
int num[N],low[N],tdfs=0;
bool bridge[N],joint[N];
void dfs(int u,int p)
{
    low[u]=num[u]=++tdfs;
    vis[u]=1;
    for (node &e:g[u]) {
        int v=e.to,pos=e.num;
        if (v==p) continue;
        if (!vis[v]) {
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]==num[v]) bridge[pos]=1;
        }
        else low[u]=min(low[u],num[v]);
    }
}
int ans[N];
node par[N];
vector<pi>require;
void dfs2(int u,int p,int stop)
{
    vis[u]=1;
    if (u==stop) return;
    for (node &e:g[u]) {
        int v=e.to,pos=e.num;
        if (vis[v]) continue;
        par[v]={u,pos,e.direct};
        dfs2(v,u,stop);
    }
}
int main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++) {int a,b; cin>>a>>b; edge.push_back({a,b}); g[a].push_back({b,i,0}); g[b].push_back({a,i,1});}
    cin>>p;
    for (int i=1;i<=p;i++) {int x,y; cin>>x>>y; require.push_back({x,y});}
    for (int i=1;i<=n;i++) if (!vis[i]) dfs(i,i);
    for (int i=1;i<=p;i++) {
        fill_n(vis,n+1,0);
        dfs2(require[i-1].fi,require[i-1].fi,require[i-1].se);
        int t=require[i-1].se;
        //cout<<t<<endl;
        while (t!=require[i-1].fi) {
            int pos=par[t].num;
            if (bridge[pos])
                ans[pos]=par[t].direct ? 2 : 1;
            t=par[t].to;
            //cout<<t<<endl;
        }
        //cout<<endl;
    }
    for (int i=1;i<=m;i++) if (ans[i]==0) cout<<"B"; else if (ans[i]==1) cout<<"R"; else cout<<"L";
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3160 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Incorrect 2 ms 3164 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3160 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Incorrect 2 ms 3164 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3164 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3164 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3160 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Incorrect 2 ms 3164 KB Output isn't correct
10 Halted 0 ms 0 KB -