oj.uz

Submission #579936

# Submission time Handle Problem Language Result Execution time Memory
579936 2022-06-20T10:06:54 Z dxz05 One-Way Streets (CEOI17_oneway) C++14
30 / 100
 3000 ms 49588 KB 
#pragma GCC optimize("Ofast,O2,O3,unroll-loops")
#pragma GCC target("avx2")

#include <bits/stdc++.h>

#include <random>

using namespace std;

void debug_out() { cerr << endl; }

template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << "[" << H << "]";
    debug_out(T...);
}

#ifdef dddxxz
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SZ(s) ((int)s.size())
#define all(x) (x).begin(), (x).end()
#define lla(x) (x).rbegin(), (x).rend()
#define bpc(x) __builtin_popcount(x)
#define bpcll(x) __builtin_popcountll(x)

clock_t startTime;

double getCurrentTime() {
    return (double) (clock() - startTime) / CLOCKS_PER_SEC;
}

#define MP make_pair

typedef long long ll;
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const double eps = 0.000001;
const int MOD = 1e9 + 7;
const int INF = 1000000101;
const long long LLINF = 1223372000000000555;
const int N = 1e6 + 3e2;
const int M = 1111;

int eu[N], ev[N];

vector<int> g[N];

int flag[N];

bool used[N];

set<pair<int, int>> bridges;

set<pair<int, int>> trash;

void bridge(int x, int y){
    if (trash.count(MP(x, y))) return;
    if (trash.count(MP(y, x))) return;
    bridges.insert(MP(x, y));
}

int tin[N], fup[N], timer = 0;
void dfs(int v, int p){
    tin[v] = fup[v] = ++timer;

    used[v] = true;
    for (int u : g[v]){
        if (u == p) continue;

        if (!used[u]){
            dfs(u, v);
            fup[v] = min(fup[v], fup[u]);
            if (fup[u] > tin[v]) bridge(u, v);
        } else {
            fup[v] = min(fup[v], tin[u]);
        }

    }
}

int p[N];

int find(int x){
    return (x == p[x] ? x : p[x] = find(p[x]));
}

void unite(int x, int y){
    x = find(x);
    y = find(y);
    if (rng() & 1) swap(x, y);
    p[x] = y;
}

void bfs(int x, vector<int> &d){
    queue<int> q;
    fill(all(d), INF);
    d[x] = 0;
    q.push(x);

    while (!q.empty()){
        x = q.front();
        q.pop();
        for (int y : g[x]){
            if (d[y] == INF){
                d[y] = d[x] + 1;
                q.push(y);
            }
        }
    }
}

map<pair<int, int>, int> mp;

void SetLeft(int x, int y){
    int i = mp.count(MP(x, y)) ? mp[MP(x, y)] : mp[MP(y, x)];
    flag[i] = 1;
}

void SetRight(int x, int y){
    int i = mp.count(MP(x, y)) ? mp[MP(x, y)] : mp[MP(y, x)];
    flag[i] = 2;
}

void solve(int TC) {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++){
        int x, y;
        cin >> x >> y;

        eu[i] = x, ev[i] = y;

        if (mp.count(MP(x, y)) || mp.count(MP(y, x))){
            int ii = (mp.count(MP(x, y)) ? mp[MP(x, y)] : mp[MP(y, x)]);
            flag[i] = flag[ii] = 3;
            trash.insert(MP(x, y));
            continue;
        }

        if (x == y){
            flag[i] = 3;
            continue;
        }

        mp[MP(x, y)] = i;

        g[x].push_back(y);
        g[y].push_back(x);
    }

    int q;
    cin >> q;

    vector<pair<int, int>> important;
    while (q--){
        int x, y;
        cin >> x >> y;
        important.emplace_back(x, y);
    }

    for (int i = 1; i <= n; i++){
        if (!used[i]) dfs(i, i);
    }

    for (int i = 1; i <= m; i++){
        int x = eu[i], y = ev[i];
        if (!bridges.count(MP(x, y)) && !bridges.count(MP(y, x))) flag[i] = 3;
    }

    auto _br = bridges;
    bridges.clear();
    for (auto now : _br){
        if (mp.find(now) == mp.end()) swap(now.first, now.second);
        bridges.insert(now);
//        cout << now.first << ' ' << now.second << endl;
    }

    iota(p + 1, p + n + 1, 1);

    for (int i = 1; i <= m; i++){
        if (flag[i] == 3) unite(eu[i], ev[i]);
    }

    for (int i = 1; i <= n; i++) g[i].clear();

    int root = n;

//    cout << endl;
//    for (int i = 1; i <= n; i++) cout << find(i) << ' ';
//    cout << endl << endl;

//    cout << find(3) << ' ' << find(4) << endl;

    for (int i = 1; i <= m; i++){
        int x = find(eu[i]), y = find(ev[i]);
        root = min({root, x, y});
        if (x != y){
            g[x].push_back(y);
            g[y].push_back(x);
//            cout << "edge " << x << ' ' << y << endl;
        }
    }

    for (auto [x, y] : important){
        int X = x, Y = y;
        x = find(x), y = find(y);

        if (x == y) continue;

        vector<int> dx(n + 1), dy(n + 1);
        bfs(x, dx);
        bfs(y, dy);

        for (auto [u, v] : bridges){
            int U = u, V = v;

//            cout << X << ' ' << Y << ' ' << U << ' ' << V << endl;

//            cout << dx[u] << ' ' << dy[v] << endl;

            u = find(u), v = find(v);

            int dist = min(dx[u] + dy[v], dx[v] + dy[u]) + 1;
            if (dist != dx[y]) continue;

            if (dx[u] + dy[v] + 1 == dist){ // x -> u -> v -> y
//                cout << "R " << X << ' ' << U << ' ' << V << ' ' << Y << endl;
                SetRight(U, V);
            } else { // x -> v -> u -> y
//                cout << "L " << X << ' ' << V << ' ' << U << ' ' << Y << endl;
                SetLeft(U, V);
            }

        }

    }

    for (int i = 1; i <= m; i++){
        if (flag[i] == 0 || flag[i] == 3) cout << 'B';
        if (flag[i] == 1) cout << 'L';
        if (flag[i] == 2) cout << 'R';
    }

}

int main() {
    startTime = clock();
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

#ifdef dddxxz
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int TC = 1;
    //    cin >> TC;

    for (int test = 1; test <= TC; test++) {
        //debug(test);
        //cout << "Case #" << test << ": ";
        solve(test);
    }

#ifdef dddxxz
    cerr << endl << "Time: " << int(getCurrentTime() * 1000) << " ms" << endl;
#endif

    return 0;
}

Compilation message

oneway.cpp: In function 'void solve(int)':
oneway.cpp:208:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  208 |     for (auto [x, y] : important){
      |               ^
oneway.cpp:218:19: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  218 |         for (auto [u, v] : bridges){
      |                   ^
oneway.cpp:209:13: warning: unused variable 'X' [-Wunused-variable]
  209 |         int X = x, Y = y;
      |             ^
oneway.cpp:209:20: warning: unused variable 'Y' [-Wunused-variable]
  209 |         int X = x, Y = y;
      |                    ^

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 14 ms 23868 KB Output is correct
3 Correct 16 ms 23892 KB Output is correct
4 Correct 16 ms 24100 KB Output is correct
5 Correct 24 ms 24128 KB Output is correct
6 Correct 14 ms 24000 KB Output is correct
7 Correct 22 ms 24020 KB Output is correct
8 Correct 21 ms 24104 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 16 ms 23892 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 14 ms 23868 KB Output is correct
3 Correct 16 ms 23892 KB Output is correct
4 Correct 16 ms 24100 KB Output is correct
5 Correct 24 ms 24128 KB Output is correct
6 Correct 14 ms 24000 KB Output is correct
7 Correct 22 ms 24020 KB Output is correct
8 Correct 21 ms 24104 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 16 ms 23892 KB Output is correct
11 Correct 137 ms 35800 KB Output is correct
12 Correct 153 ms 37136 KB Output is correct
13 Correct 224 ms 38804 KB Output is correct
14 Correct 326 ms 41536 KB Output is correct
15 Correct 459 ms 42568 KB Output is correct
16 Correct 397 ms 46844 KB Output is correct
17 Execution timed out 3041 ms 49588 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23892 KB Output is correct
2 Correct 14 ms 23868 KB Output is correct
3 Correct 16 ms 23892 KB Output is correct
4 Correct 16 ms 24100 KB Output is correct
5 Correct 24 ms 24128 KB Output is correct
6 Correct 14 ms 24000 KB Output is correct
7 Correct 22 ms 24020 KB Output is correct
8 Correct 21 ms 24104 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 16 ms 23892 KB Output is correct
11 Correct 137 ms 35800 KB Output is correct
12 Correct 153 ms 37136 KB Output is correct
13 Correct 224 ms 38804 KB Output is correct
14 Correct 326 ms 41536 KB Output is correct
15 Correct 459 ms 42568 KB Output is correct
16 Correct 397 ms 46844 KB Output is correct
17 Execution timed out 3041 ms 49588 KB Time limit exceeded
18 Halted 0 ms 0 KB -