oj.uz

Submission #1027342

# Submission time Handle Problem Language Result Execution time Memory
1027342 2024-07-19T03:50:24 Z ojnewbie111 One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 13284 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;
    bool p_skip=0;
    for (node &e:g[u]) {
        int v=e.to,pos=e.num;
        if (v==p && !p_skip) {p_skip=1; continue;}
        if (!num[v]) {
            dfs(v,u);
            low[u]=min(low[u],low[v]);
            if (low[v]>num[u]) bridge[pos]=1;
            //if (pos==447) cout<<low[v]<<" "<<num[v]<<endl;
        }
        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()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    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);
    //cout<<bridge[447]<<endl;
    for (int i=1;i<=p;i++) {
        fill_n(vis,n+1,0);
        for (int i=1;i<=n;i++) par[i]={0,0,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; //cout<<t<<" "<<par[t].to<<" "<<pos<<" "<<bridge[pos]<<endl;
            t=par[t].to;
            //cout<<t<<endl;
        }
        //cout<<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
30.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 3212 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 2 ms 3160 KB Output is correct

Subtask #2
30.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 3212 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 2 ms 3160 KB Output is correct
11 Correct 158 ms 9472 KB Output is correct
12 Correct 222 ms 10692 KB Output is correct
13 Correct 305 ms 11284 KB Output is correct
14 Correct 382 ms 11988 KB Output is correct
15 Correct 337 ms 12128 KB Output is correct
16 Correct 55 ms 9928 KB Output is correct
17 Correct 312 ms 12440 KB Output is correct
18 Correct 344 ms 10348 KB Output is correct
19 Correct 280 ms 12872 KB Output is correct
20 Correct 256 ms 9772 KB Output is correct
21 Correct 207 ms 9932 KB Output is correct

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 3212 KB Output is correct
6 Correct 2 ms 3164 KB Output is correct
7 Correct 2 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 2 ms 3160 KB Output is correct
11 Correct 158 ms 9472 KB Output is correct
12 Correct 222 ms 10692 KB Output is correct
13 Correct 305 ms 11284 KB Output is correct
14 Correct 382 ms 11988 KB Output is correct
15 Correct 337 ms 12128 KB Output is correct
16 Correct 55 ms 9928 KB Output is correct
17 Correct 312 ms 12440 KB Output is correct
18 Correct 344 ms 10348 KB Output is correct
19 Correct 280 ms 12872 KB Output is correct
20 Correct 256 ms 9772 KB Output is correct
21 Correct 207 ms 9932 KB Output is correct
22 Execution timed out 3077 ms 13284 KB Time limit exceeded
23 Halted 0 ms 0 KB -