oj.uz

Submission #1027343

# Submission time Handle Problem Language Result Execution time Memory
1027343 2024-07-19T03:51:21 Z ojnewbie111 One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 13388 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#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 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3224 KB Output is correct
5 Correct 2 ms 3164 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 3296 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3224 KB Output is correct
5 Correct 2 ms 3164 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 3296 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 157 ms 9680 KB Output is correct
12 Correct 226 ms 10860 KB Output is correct
13 Correct 308 ms 11976 KB Output is correct
14 Correct 382 ms 12660 KB Output is correct
15 Correct 371 ms 12484 KB Output is correct
16 Correct 60 ms 9956 KB Output is correct
17 Correct 311 ms 11988 KB Output is correct
18 Correct 300 ms 10288 KB Output is correct
19 Correct 317 ms 13388 KB Output is correct
20 Correct 279 ms 10008 KB Output is correct
21 Correct 236 ms 10184 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 3160 KB Output is correct
2 Correct 1 ms 3164 KB Output is correct
3 Correct 2 ms 3164 KB Output is correct
4 Correct 2 ms 3224 KB Output is correct
5 Correct 2 ms 3164 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 3296 KB Output is correct
9 Correct 2 ms 3164 KB Output is correct
10 Correct 2 ms 3164 KB Output is correct
11 Correct 157 ms 9680 KB Output is correct
12 Correct 226 ms 10860 KB Output is correct
13 Correct 308 ms 11976 KB Output is correct
14 Correct 382 ms 12660 KB Output is correct
15 Correct 371 ms 12484 KB Output is correct
16 Correct 60 ms 9956 KB Output is correct
17 Correct 311 ms 11988 KB Output is correct
18 Correct 300 ms 10288 KB Output is correct
19 Correct 317 ms 13388 KB Output is correct
20 Correct 279 ms 10008 KB Output is correct
21 Correct 236 ms 10184 KB Output is correct
22 Execution timed out 3043 ms 13040 KB Time limit exceeded
23 Halted 0 ms 0 KB -