oj.uz

Submission #468125

# Submission time Handle Problem Language Result Execution time Memory
468125 2021-08-26T19:12:51 Z Vladth11 One-Way Streets (CEOI17_oneway) C++14
100 / 100
 235 ms 26552 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast,unroll-loops")

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <long double, pii> muchie;
typedef tree <ll, null_type, less_equal <ll>, rb_tree_tag, tree_order_statistics_node_update> OST;

const ll NMAX = 100001;
const ll INF = (1LL << 60);
const ll HALF = (1LL << 59);
const ll MOD = 30013;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 21;

int n, m;
int lvl[NMAX];
int dp[NMAX];
int viz[NMAX];
int cnt;
int dest[NMAX];
int sursa[NMAX];
int surse[NMAX];
int deste[NMAX];
int comp[NMAX];
int parent[NMAX];
int bl[NMAX][nr_of_bits + 1];
vector <int> v[NMAX];
int stamp;
pii timp[NMAX];

bool par(int a, int b){
    return timp[a].first <= timp[b].first && timp[b].second <= timp[a].second;
}

void DFS(int node, int p){
    lvl[node] = lvl[p] + 1;
    parent[node] = p;
    for(auto x : v[node]){
        if(!lvl[x]){
            DFS(x, node);
            dp[node] += dp[x];
        }else if(lvl[x] > lvl[node]){
            dp[node]--;
        }else{
            dp[node]++;
        }
    }
    if(lvl[node] != 1)
        dp[node]--;
}

void assignComp(int node, int p){
    if(!dp[node]){
        cnt++;
        timp[cnt].first = ++stamp;
        comp[node] = cnt;
        if(comp[p] != 0){
            bl[comp[node]][0] = comp[p];
        }
    }else{
        comp[node] = comp[p]; ///nu cnttt ca se modifica
    }
    for(auto x : v[node]){
        if(!comp[x]){
            assignComp(x, node);
        }
    }
    timp[comp[node]].second = stamp;
}

pii special[NMAX];
pii edges[NMAX];

void calc(int node, int p){
    viz[node] = 1;
    for(auto x : v[node]){
        if(!viz[x]){
            calc(x, node);
            if(comp[node] != comp[x]){
                surse[comp[node]] += surse[comp[x]];
                deste[comp[node]] += deste[comp[x]];
            }
        }
    }
}

int lca(int a, int b){
    int r = a;
    int pas = nr_of_bits;
    while(pas >= 0){
        int nxt = bl[r][pas];
        if(nxt != 0 && !par(nxt, b))
            r = nxt;
        pas--;
    }
    if(!par(r, b))
        r = bl[r][0];
    return r;
}

int main() {
    int i;
    /// Poate sunt mai multe componente
    cin >> n >> m;
    for(i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
        edges[i] = {x, y};
    }
    for(i = 1; i <= n; i++)
        if(!lvl[i])
            DFS(i, 0);
    for(i = 1; i <= n; i++)
        if(!comp[i])
            assignComp(i, 0);
    for(int j = 1; j <= nr_of_bits; j++){
        for(int i = 1; i <= n; i++){
            bl[i][j] = bl[bl[i][j - 1]][j - 1];
        }
    }
    int q;
    cin >> q;
    for(i = 1; i <= q; i++){
        int x, y;
        cin >> x >> y;
        special[i] = {x, y};
        if(comp[x] == comp[y])
            continue;
        if(par(comp[x], comp[y])){
            deste[comp[y]]++;
            ///se termina de adunat la
            deste[comp[x]]--;
            continue;
        }
        if(par(comp[y], comp[x])){
            surse[comp[x]]++;
            ///se termina de adunat la
            surse[comp[y]]--;
            continue;
        }
        surse[comp[x]]++;
        deste[comp[y]]++;
        deste[lca(comp[x], comp[y])]--;
        surse[lca(comp[x], comp[y])]--;
    }
    for(i = 1; i <= n; i++){
        if(!viz[i])
            calc(i, 0);
    }
    for(i = 1; i <= m; i++){
        int x = edges[i].first;
        int y = edges[i].second;
        if(lvl[x] > lvl[y]){
            swap(x, y);
        }
        if(parent[y] != x){
            cout << "B";
            continue;
        }
        if(dp[y] != 0){
            cout << "B";
            continue;
        }
        if(!deste[comp[y]] && !surse[comp[y]]){
            cout << "B";
            continue;
        }
        if(surse[comp[y]] > 0){
            if(y == edges[i].first){
                cout << "R";
            }else{
                cout << "L";
            }
            continue;
        }
        if(y == edges[i].first){
            cout << "L";
        }else{
            cout << "R";
        }
    }
    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 86 ms 9232 KB Output is correct
12 Correct 97 ms 11292 KB Output is correct
13 Correct 124 ms 14440 KB Output is correct
14 Correct 124 ms 18408 KB Output is correct
15 Correct 132 ms 19572 KB Output is correct
16 Correct 134 ms 20040 KB Output is correct
17 Correct 137 ms 21612 KB Output is correct
18 Correct 133 ms 19980 KB Output is correct
19 Correct 126 ms 22724 KB Output is correct
20 Correct 100 ms 13064 KB Output is correct
21 Correct 98 ms 12800 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2764 KB Output is correct
4 Correct 3 ms 2764 KB Output is correct
5 Correct 3 ms 2892 KB Output is correct
6 Correct 3 ms 2764 KB Output is correct
7 Correct 3 ms 2892 KB Output is correct
8 Correct 3 ms 2764 KB Output is correct
9 Correct 3 ms 2764 KB Output is correct
10 Correct 3 ms 2764 KB Output is correct
11 Correct 86 ms 9232 KB Output is correct
12 Correct 97 ms 11292 KB Output is correct
13 Correct 124 ms 14440 KB Output is correct
14 Correct 124 ms 18408 KB Output is correct
15 Correct 132 ms 19572 KB Output is correct
16 Correct 134 ms 20040 KB Output is correct
17 Correct 137 ms 21612 KB Output is correct
18 Correct 133 ms 19980 KB Output is correct
19 Correct 126 ms 22724 KB Output is correct
20 Correct 100 ms 13064 KB Output is correct
21 Correct 98 ms 12800 KB Output is correct
22 Correct 232 ms 23520 KB Output is correct
23 Correct 233 ms 21852 KB Output is correct
24 Correct 224 ms 22084 KB Output is correct
25 Correct 218 ms 26552 KB Output is correct
26 Correct 227 ms 23068 KB Output is correct
27 Correct 235 ms 21988 KB Output is correct
28 Correct 92 ms 6568 KB Output is correct
29 Correct 167 ms 14644 KB Output is correct
30 Correct 165 ms 14696 KB Output is correct
31 Correct 182 ms 15180 KB Output is correct
32 Correct 179 ms 18908 KB Output is correct