oj.uz

Submission #425875

# Submission time Handle Problem Language Result Execution time Memory
425875 2021-06-13T12:08:23 Z oleh1421 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 16268 KB 
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100010;
const ll mod=1000000007;
const ll inf=1e15;
int a[N],b[N];
int x[N],y[N];
vector<pair<int,int> >g[N];
int timer=0;
int tin[N],tout[N],fup[N];
bool used[N];
bool imp[N];
void dfs(int v,int pr){
    used[v]=true;
    tin[v]=fup[v]=++timer;
    for (auto cur:g[v]){
        int to=cur.first;
        int ind=cur.second;
        if (ind==pr) continue;
        if (!used[to]){
            dfs(to,ind);
            if (fup[to]>tin[v]) imp[ind]=true;
            fup[v]=min(fup[v],fup[to]);
        } else {
            fup[v]=min(fup[v],tin[to]);
        }
    }
}
int comp[N];
int num=0;
void dfs1(int v){
    comp[v]=num;
    for (auto cur:g[v]){
        int to=cur.first;
        int ind=cur.second;
        if (!imp[ind] && !comp[to]){
            dfs1(to);
        }
    }
}
vector<pair<int,int> >t[N];
const int L=20;
int up[N][L];

void dfs2(int v,int pr){
    up[v][0]=pr;
//    cout<<"0 "<<v<<" "<<pr<<endl;
    for (int i=1;i<L;i++){
        up[v][i]=up[up[v][i-1]][i-1];

    }
    used[v]=true;
    tin[v]=++timer;
    for (auto cur:t[v]){
        int to=cur.first;
        int ind=cur.second;
        if (to==pr) continue;
        dfs2(to,v);
    }

    tout[v]=timer;
}
bool upper(int a,int b){
    return (tin[a]<=tin[b] && tout[b]<=tout[a]);
}
int lca(int a,int b){
    if (upper(a,b)) return a;
    if (upper(b,a)) return b;
    for (int i=L-1;i>=0;i--){
        if (!upper(up[a][i],b)) a=up[a][i];
    }
    return up[a][0];
}
int add[N][2];
char ans[N];
void dfs3(int v,int pr,int ind){
    used[v]=true;
    for (auto cur:t[v]){
        int to=cur.first;
        int ind=cur.second;
        if (to==pr) continue;
        dfs3(to,v,ind);
        add[v][0]+=add[to][0];
        add[v][1]+=add[v][1];
    }
//    if (add[v][0] && add[v][1]) exit(1);
    if (add[v][0]){
        if (comp[a[ind]]==v) ans[ind]='R';
        else ans[ind]='L';
    } else if (add[v][1]){
        if (comp[a[ind]]==v) ans[ind]='L';
        else ans[ind]='R';
    } else {

    }

}
pair<int,int> p[N];
void dfs4(int v){
    used[v]=true;
    for (auto cur:g[v]){
        int to=cur.first;
        int ind=cur.second;
        if (used[to]) continue;
        p[to]={v,ind};
        dfs4(to);
    }

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n,m;cin>>n>>m;
    for (int i=1;i<=m;i++){
        cin>>a[i]>>b[i];
        g[a[i]].push_back({b[i],i});
        g[b[i]].push_back({a[i],i});
        ans[i]='B';
    }
    int k;cin>>k;
    for (int i=1;i<=k;i++){
        cin>>x[i]>>y[i];
    }
    for (int i=1;i<=n;i++){
        if (!used[i]){
            dfs(i,0);
        }
    }
    for (int i=1;i<=k;i++){
        for (int j=1;j<=n;j++) used[j]=false;
        dfs4(x[i]);
        int cur=y[i];
        while (cur!=x[i]){
            int to=p[cur].first;
            int ind=p[cur].second;
            if (imp[ind]){
                if (a[ind]==to) ans[ind]='R';
                else ans[ind]='L';
            }
            cur=to;
        }
    }
//    for (int i=1;i<=n;i++){
//        if (!comp[i]){
//            num++;
//            dfs1(i);
//        }
//    }
//    for (int v=1;v<=n;v++){
//        for (auto cur:g[v]){
//            int to=cur.first;
//            int ind=cur.second;
//            if (imp[ind]){
//                t[comp[v]].push_back({comp[to],ind});
//            }
//        }
//    }
//    for (int i=1;i<=n;i++) used[i]=false,tin[i]=0;
//    tin[0]=0;
//    timer=0;
//    for (int i=1;i<=num;i++){
//        if (!used[i]) dfs2(i,0);
//    }
//    tout[0]=timer;
//    for (int i=1;i<=k;i++){
//        x[i]=comp[x[i]];
//        y[i]=comp[y[i]];
//        int lc=lca(x[i],y[i]);
//        add[x[i]][0]++;
//        add[y[i]][1]++;
//        add[lc][0]--;
//        add[lc][1]--;
//    }
//    for (int i=1;i<=num;i++) used[i]=false;
//    for (int i=1;i<=num;i++) {
//        if (!used[i]){
//            dfs3(i,0,0);
//        }
//    }
    for (int i=1;i<=m;i++) cout<<ans[i];
    cout<<endl;
    return 0;
}

Compilation message

oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:57:13: warning: unused variable 'ind' [-Wunused-variable]
   57 |         int ind=cur.second;
      |             ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 6 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 6 ms 5144 KB Output is correct
6 Correct 6 ms 5092 KB Output is correct
7 Correct 7 ms 5168 KB Output is correct
8 Correct 6 ms 5068 KB Output is correct
9 Correct 7 ms 5068 KB Output is correct
10 Correct 7 ms 5040 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 6 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 6 ms 5144 KB Output is correct
6 Correct 6 ms 5092 KB Output is correct
7 Correct 7 ms 5168 KB Output is correct
8 Correct 6 ms 5068 KB Output is correct
9 Correct 7 ms 5068 KB Output is correct
10 Correct 7 ms 5040 KB Output is correct
11 Correct 199 ms 11244 KB Output is correct
12 Correct 338 ms 12336 KB Output is correct
13 Correct 482 ms 13476 KB Output is correct
14 Correct 923 ms 14292 KB Output is correct
15 Correct 809 ms 14360 KB Output is correct
16 Correct 88 ms 12612 KB Output is correct
17 Correct 736 ms 14252 KB Output is correct
18 Correct 862 ms 12564 KB Output is correct
19 Correct 511 ms 15224 KB Output is correct
20 Correct 380 ms 12040 KB Output is correct
21 Correct 339 ms 11840 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5068 KB Output is correct
2 Correct 4 ms 4940 KB Output is correct
3 Correct 6 ms 5068 KB Output is correct
4 Correct 4 ms 5068 KB Output is correct
5 Correct 6 ms 5144 KB Output is correct
6 Correct 6 ms 5092 KB Output is correct
7 Correct 7 ms 5168 KB Output is correct
8 Correct 6 ms 5068 KB Output is correct
9 Correct 7 ms 5068 KB Output is correct
10 Correct 7 ms 5040 KB Output is correct
11 Correct 199 ms 11244 KB Output is correct
12 Correct 338 ms 12336 KB Output is correct
13 Correct 482 ms 13476 KB Output is correct
14 Correct 923 ms 14292 KB Output is correct
15 Correct 809 ms 14360 KB Output is correct
16 Correct 88 ms 12612 KB Output is correct
17 Correct 736 ms 14252 KB Output is correct
18 Correct 862 ms 12564 KB Output is correct
19 Correct 511 ms 15224 KB Output is correct
20 Correct 380 ms 12040 KB Output is correct
21 Correct 339 ms 11840 KB Output is correct
22 Execution timed out 3065 ms 16268 KB Time limit exceeded
23 Halted 0 ms 0 KB -