oj.uz

Submission #266456

# Submission time Handle Problem Language Result Execution time Memory
266456 2020-08-15T09:51:45 Z MarcoMeijer One-Way Streets (CEOI17_oneway) C++14
100 / 100
 1195 ms 101384 KB 
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi,' ',x.se);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }
template<class H> void OUTLS(const H& h) {OUTL(h); }
template<class H, class... T> void OUTLS(const H& h, const T&... t) {OUT(h,' '); OUTLS(t...); }

//===================//
//  Added libraries  //
//===================//

//===================//
//end added libraries//
//===================//

void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}


//===================//
//   begin program   //
//===================//

const int MX = 3e5;

int n, m, p;
int a[MX], b[MX], x[MX], y[MX];
bitset<MX> visited, inside;
vi adj[MX];
vi dir[MX], rev[MX];
stack<int> stck;
int comp[MX], compN=0;
set<ii> adjComp[MX];
map<ii,int> adjCEW;
map<ii,int> pToEdge;
string ans;
map<ii,int> cnt;
int added[MX];

void dfsDir(int u, int p=-1) {
    if(visited[u]) return;
    visited[u] = 1;
    inside[u] = 1;
    FOR(v,adj[u]) if(v != p) {
        if(!visited[v] || inside[v]) {
            dir[u].pb(v);
            rev[v].pb(u);
            if(cnt[{u,v}] >= 2) {
                dir[v].pb(u);
                rev[u].pb(v);
            }
        }
        if(!visited[v]) dfsDir(v, u);
    }
    inside[u] = 0;
}
void dfsSCC1(int u) {
    if(visited[u]) return;
    visited[u] = 1;
    FOR(v,dir[u]) dfsSCC1(v);
    stck.push(u);
}
void dfsSCC2(int u) {
    if(visited[u]) return;
    visited[u] = 1;
    FOR(v,rev[u]) dfsSCC2(v);
    comp[u] = compN;
}
void findSCC() {
    visited.reset();
    RE1(i,n) dfsSCC1(i);

    visited.reset();
    while(!stck.empty()) {
        int u = stck.top(); stck.pop();
        if(visited[u]) continue;
        dfsSCC2(u);
        compN++;
    }

    RE1(u,n) {
        FOR(v,adj[u]) {
            if(comp[u] != comp[v]) {
                adjComp[comp[u]].insert({comp[v],pToEdge[{u,v}]});
                adjComp[comp[v]].insert({comp[u],pToEdge[{u,v}]});
            }
        }
    }
}

int PC[MX];
void dfsPC(int u, int p=-1) {
    visited[u] = 1;
    PC[u] = p;
    FOR(v,adjComp[u]) if(v.fi != p) {
        dfsPC(v.fi,u);
    }
}

int SM[MX];
void dfsAns(int u, int p=-1) {
    SM[u] = 0;
    FOR(v,adjComp[u]) if(v.fi != p) {
        dfsAns(v.fi, u);
        int tot = SM[v.fi] + adjCEW[{u,v.fi}];
        SM[u] += tot;
        int e = v.se;
        if(tot != 0) ans[e] = 'R';
        if(tot > 0) {
            // v -> u
            if(comp[a[e]] != v.fi) ans[e] = 'L';
        }
        if(tot < 0) {
            // u -> v
            if(comp[a[e]] != u) ans[e] = 'L';
        }
    }
}

void program() {
    IN(n,m);
    RE(i,m) {
        int u, v;
        IN(u,v);
        adj[u].pb(v);
        adj[v].pb(u);
        a[i] = u;
        b[i] = v;
        pToEdge[{u,v}] = i;
        pToEdge[{v,u}] = i;
        cnt[{u,v}]++;
        cnt[{v,u}]++;
    }
    IN(p);
    RE(i,p) {
        IN(x[i],y[i]);
    }

    visited.reset();
    RE1(i,n) dfsDir(i);
    
    findSCC();

    ans.assign(m,'X');
    RE(i,m) ans[i] = 'B';

    visited.reset();
    vi roots;
    RE(i,compN) if(!visited[i]) {
        dfsPC(i);
        roots.pb(i);
    }
    RE(i,p) {
        int u=comp[x[i]], v=comp[y[i]];

        // u -> LCA
        adjCEW[{u,PC[u]}]++;
        adjCEW[{PC[u],u}]++;
        
        // LCA -> v
        adjCEW[{v,PC[v]}]--;
        adjCEW[{PC[v],v}]--;
    }
    FOR(i,roots) dfsAns(i);

    OUTL(ans);
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35584 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 27 ms 35968 KB Output is correct
4 Correct 28 ms 36272 KB Output is correct
5 Correct 28 ms 36224 KB Output is correct
6 Correct 24 ms 35840 KB Output is correct
7 Correct 25 ms 36224 KB Output is correct
8 Correct 28 ms 36224 KB Output is correct
9 Correct 28 ms 35968 KB Output is correct
10 Correct 28 ms 35960 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35584 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 27 ms 35968 KB Output is correct
4 Correct 28 ms 36272 KB Output is correct
5 Correct 28 ms 36224 KB Output is correct
6 Correct 24 ms 35840 KB Output is correct
7 Correct 25 ms 36224 KB Output is correct
8 Correct 28 ms 36224 KB Output is correct
9 Correct 28 ms 35968 KB Output is correct
10 Correct 28 ms 35960 KB Output is correct
11 Correct 517 ms 66516 KB Output is correct
12 Correct 745 ms 67960 KB Output is correct
13 Correct 553 ms 70252 KB Output is correct
14 Correct 730 ms 74872 KB Output is correct
15 Correct 604 ms 76400 KB Output is correct
16 Correct 739 ms 86472 KB Output is correct
17 Correct 869 ms 88984 KB Output is correct
18 Correct 836 ms 86532 KB Output is correct
19 Correct 704 ms 90308 KB Output is correct
20 Correct 544 ms 68728 KB Output is correct
21 Correct 506 ms 67196 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 35584 KB Output is correct
2 Correct 25 ms 35584 KB Output is correct
3 Correct 27 ms 35968 KB Output is correct
4 Correct 28 ms 36272 KB Output is correct
5 Correct 28 ms 36224 KB Output is correct
6 Correct 24 ms 35840 KB Output is correct
7 Correct 25 ms 36224 KB Output is correct
8 Correct 28 ms 36224 KB Output is correct
9 Correct 28 ms 35968 KB Output is correct
10 Correct 28 ms 35960 KB Output is correct
11 Correct 517 ms 66516 KB Output is correct
12 Correct 745 ms 67960 KB Output is correct
13 Correct 553 ms 70252 KB Output is correct
14 Correct 730 ms 74872 KB Output is correct
15 Correct 604 ms 76400 KB Output is correct
16 Correct 739 ms 86472 KB Output is correct
17 Correct 869 ms 88984 KB Output is correct
18 Correct 836 ms 86532 KB Output is correct
19 Correct 704 ms 90308 KB Output is correct
20 Correct 544 ms 68728 KB Output is correct
21 Correct 506 ms 67196 KB Output is correct
22 Correct 1195 ms 95172 KB Output is correct
23 Correct 906 ms 95380 KB Output is correct
24 Correct 1063 ms 95008 KB Output is correct
25 Correct 805 ms 101384 KB Output is correct
26 Correct 857 ms 96916 KB Output is correct
27 Correct 810 ms 95300 KB Output is correct
28 Correct 140 ms 42488 KB Output is correct
29 Correct 588 ms 71288 KB Output is correct
30 Correct 495 ms 71376 KB Output is correct
31 Correct 735 ms 71892 KB Output is correct
32 Correct 558 ms 75256 KB Output is correct