oj.uz

Submission #35491

# Submission time Handle Problem Language Result Execution time Memory
35491 2017-11-23T01:09:58 Z imaxblue One-Way Streets (CEOI17_oneway) C++14
100 / 100
 769 ms 44788 KB 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int> 
#define pb push_back
#define x first
#define y second
#define lb lower_bound
#define mp make_pair
int n, m, p, com[100005], pre[100005], num[100005], c, a, b;
int par[20][100005], d[100005], one[100005], dir[100005];
vector<pii> st[100005];
vector<pii> v[100005], w[100005];
vector<int> vis;
void dfs(int N, int P){
    if (num[N]!=0) return;
    num[N]=(pre[N]=++c);
    //if (num[N]==1) exit(2);
    vis.pb(N);
    for (int l=0; l<v[N].size(); ++l){
        if (v[N][l].x==P) {P=-1; continue;}
        dfs(v[N][l].x, N);
        pre[N]=min(pre[N], pre[v[N][l].x]);
    }
    if (pre[N]==num[N]){
        int t=-1;
        do{
            t=vis.back(); vis.pop_back();
            com[t]=N;
            //cout << N << ' ' << t << endl;
            for (int l=0; l<v[t].size(); ++l){
                w[N].pb(v[t][l]);
            }
        } while(t!=N);
    }
}
void dfs2(int N, int P){
    N=com[N];
    if (P==-1) d[N]=1; else d[N]=d[P]+1;
    for (int l=0; l<20; ++l) par[l][N]=-1;
    par[0][N]=P;
    int k=0;
    while(par[k][N]!=-1){
        par[k+1][N]=par[k][par[k][N]]; ++k;
    }
    for (int l=0; l<w[N].size(); ++l){
        w[N][l].x=com[w[N][l].x];
        if (w[N][l].x==N || w[N][l].x==P) continue;
        dfs2(w[N][l].x, N);
    }
}
void lca(int a, int b){
    int A=(a=com[a]), B=(b=com[b]), k=19;
    if (a==b) return;
    while(d[A]>d[B]){
        //cout << A << ' ' << d[A] << endl;
        while(k>0 && (d[A]-(1 << k)<d[B])) k--;
        A=par[k][A];
    }
    while(d[B]>d[A]){
        //cout << B << ' ' << d[B] << endl;
        while(k>0 && (d[B]-(1 << k)<d[A])) k--;
        B=par[k][B];
    }
    k=19;
    while(A!=B){
        while(k>0 && par[k][A]==par[k][B]){
            --k;
        }
        A=par[k][A]; B=par[k][B];
        //cout << k << ' ' << A << ' ' << B << endl;
    }
    //cout << A << ' ' <<B << endl;return;
    st[a].pb(mp(A, 1));
    st[b].pb(mp(A, 0));
    //cout << a << ' ' << A << ' ' << b << endl;
}
multiset<int> s[2];
void dfs3(int N, int P){
    N=com[N]; com[N]=0;
    for (int l=0; l<st[N].size(); ++l){
        s[st[N][l].y].insert(st[N][l].x);
    }
    //cout << N << ' ' << s[0].size()<< ' ' << s[1].size() << endl;
    int a, b, t;
    for (int l=0; l<w[N].size(); ++l){
        if (w[N][l].x==N || w[N][l].x==P) continue;
        a=s[0].size(); b=s[1].size();
        dfs3(w[N][l].x, N);
        t=0;
        //if (s[0].size()>a && s[1].size()>b) exit(1);
        if (s[0].size()>a) t=1;
        if (s[1].size()>b) t=2;
        if (w[N][l].y<0){
            t=(3-t)%3; w[N][l].y*=-1;
        }
        //cout << N << ' ' << w[N][l].x << ' ' << P << ' ' << t << ' ' << w[N][l].y << endl;
        dir[w[N][l].y]=t;
    }
    s[0].erase(N); s[1].erase(N);
}
int dist[100005][2], r[100005];
queue<pii> q; 
bool dfs4(int N, int P, int D){
    N=com[N]; num[N]=0;
    if (N==D) return 1;
    for (int l=0; l<w[N].size(); ++l){
        w[N][l].x=com[w[N][l].x];
        if (w[N][l].x==P || w[N][l].x==N) continue;
        if (dfs4(w[N][l].x, N, D)){
            //cout << N << ' ' << w[N][l].x << endl;
            dir[abs(w[N][l].y)]=(w[N][l].y<0)+1;
            //cout << "*" << endl;
            return 1;
        }
    }
    return 0;
}
void bfs(int A, int B){
    dfs4(com[A], -1, com[B]);
}
int main() {
    cin >> n >> m;
    for (int l=0; l<m; ++l){
        cin >> a >> b;
        v[a].pb(mp(b, l+1)); v[b].pb(mp(a, -l-1));
    }
    for (int l=1; l<=n; ++l)
        if (num[l]==0)
            dfs(l, -1);
    cin >> p;
    if (p<=100 && 0){
        for (int l=0; l<p; ++l){
            cin >> a >> b;
            bfs(a, b);
        }
    } else {
        
    for (int l=1; l<=n; ++l)
        if (par[0][com[l]]==0)
            dfs2(com[l], -1);
        for (int l=0; l<p; ++l){
            cin >> a >> b;
            lca(a, b);
        }
    for (int l=1; l<=n; ++l)
        if (num[com[l]]!=0)
            dfs3(com[l], -1);
    }
    for (int l=1; l<=m; ++l){
        if (dir[l]==0) cout << "B";
        else if (dir[l]==1) cout << "R";
        else if (dir[l]==2) cout << "L";
        else return 1;
    }
    return 0;
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:20:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<v[N].size(); ++l){
                    ^
oneway.cpp:31:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int l=0; l<v[t].size(); ++l){
                            ^
oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:46:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<w[N].size(); ++l){
                    ^
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:81:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<st[N].size(); ++l){
                    ^
oneway.cpp:86:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<w[N].size(); ++l){
                    ^
oneway.cpp:92:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (s[0].size()>a) t=1;
                        ^
oneway.cpp:93:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (s[1].size()>b) t=2;
                        ^
oneway.cpp: In function 'bool dfs4(int, int, int)':
oneway.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int l=0; l<w[N].size(); ++l){
                    ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20384 KB Output is correct
2 Correct 0 ms 20384 KB Output is correct
3 Correct 0 ms 20516 KB Output is correct
4 Correct 3 ms 20516 KB Output is correct
5 Correct 3 ms 20516 KB Output is correct
6 Correct 3 ms 20520 KB Output is correct
7 Correct 0 ms 20516 KB Output is correct
8 Correct 9 ms 20516 KB Output is correct
9 Correct 6 ms 20520 KB Output is correct
10 Correct 6 ms 20516 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20384 KB Output is correct
2 Correct 0 ms 20384 KB Output is correct
3 Correct 0 ms 20516 KB Output is correct
4 Correct 3 ms 20516 KB Output is correct
5 Correct 3 ms 20516 KB Output is correct
6 Correct 3 ms 20520 KB Output is correct
7 Correct 0 ms 20516 KB Output is correct
8 Correct 9 ms 20516 KB Output is correct
9 Correct 6 ms 20520 KB Output is correct
10 Correct 6 ms 20516 KB Output is correct
11 Correct 153 ms 27244 KB Output is correct
12 Correct 166 ms 27868 KB Output is correct
13 Correct 176 ms 28664 KB Output is correct
14 Correct 229 ms 29368 KB Output is correct
15 Correct 209 ms 29552 KB Output is correct
16 Correct 299 ms 27908 KB Output is correct
17 Correct 299 ms 29232 KB Output is correct
18 Correct 256 ms 27908 KB Output is correct
19 Correct 259 ms 30544 KB Output is correct
20 Correct 143 ms 27800 KB Output is correct
21 Correct 123 ms 26332 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 20384 KB Output is correct
2 Correct 0 ms 20384 KB Output is correct
3 Correct 0 ms 20516 KB Output is correct
4 Correct 3 ms 20516 KB Output is correct
5 Correct 3 ms 20516 KB Output is correct
6 Correct 3 ms 20520 KB Output is correct
7 Correct 0 ms 20516 KB Output is correct
8 Correct 9 ms 20516 KB Output is correct
9 Correct 6 ms 20520 KB Output is correct
10 Correct 6 ms 20516 KB Output is correct
11 Correct 153 ms 27244 KB Output is correct
12 Correct 166 ms 27868 KB Output is correct
13 Correct 176 ms 28664 KB Output is correct
14 Correct 229 ms 29368 KB Output is correct
15 Correct 209 ms 29552 KB Output is correct
16 Correct 299 ms 27908 KB Output is correct
17 Correct 299 ms 29232 KB Output is correct
18 Correct 256 ms 27908 KB Output is correct
19 Correct 259 ms 30544 KB Output is correct
20 Correct 143 ms 27800 KB Output is correct
21 Correct 123 ms 26332 KB Output is correct
22 Correct 769 ms 41240 KB Output is correct
23 Correct 586 ms 38996 KB Output is correct
24 Correct 579 ms 38468 KB Output is correct
25 Correct 769 ms 44788 KB Output is correct
26 Correct 733 ms 40304 KB Output is correct
27 Correct 603 ms 37988 KB Output is correct
28 Correct 93 ms 25720 KB Output is correct
29 Correct 219 ms 34288 KB Output is correct
30 Correct 266 ms 36108 KB Output is correct
31 Correct 226 ms 31528 KB Output is correct
32 Correct 539 ms 40208 KB Output is correct