oj.uz

Submission #579943

# Submission time Handle Problem Language Result Execution time Memory
579943 2022-06-20T10:25:18 Z dxz05 One-Way Streets (CEOI17_oneway) C++17
60 / 100
 3000 ms 50880 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;

inline 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;
inline 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];

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

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

int q[N];
inline void bfs(int x, vector<int> &d){
    fill(all(d), INF);
    d[x] = 0;
    int sz = 1;
    q[0] = x;

    for (int i = 0; i < sz; i++){
        x = q[i];
        for (int y : g[x]){
            if (d[y] == INF){
                d[y] = d[x] + 1;
                q[sz++] = 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;
}

char answer[N];
inline void solve(int TC) {
    int n, m;
    scanf("%d %d", &n, &m);

    for (int i = 1; i <= m; i++){
        int x, y;
        scanf("%d %d", &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 qu;
    scanf("%d", &qu);

    vector<pair<int, int>> important;
    while (qu--){
        int x, y;
        scanf("%d %d", &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);
    }

    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;

    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);
        }
    }

    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);

        vector<pair<int, int>> del;
        for (auto [u, v] : bridges){
            int U = u, V = v;

            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){
                SetRight(U, V);
            } else {
                SetLeft(U, V);
            }

            del.push_back(MP(U, V));

        }

        for (auto now : del) bridges.erase(now);

    }

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

    printf("%s", answer);

}

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:203:13: warning: unused variable 'X' [-Wunused-variable]
  203 |         int X = x, Y = y;
      |             ^
oneway.cpp:203:20: warning: unused variable 'Y' [-Wunused-variable]
  203 |         int X = x, Y = y;
      |                    ^
oneway.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:135:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |     scanf("%d", &qu);
      |     ~~~~~^~~~~~~~~~~
oneway.cpp:163:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |         scanf("%d %d", &x, &y);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 15 ms 23796 KB Output is correct
3 Correct 15 ms 23928 KB Output is correct
4 Correct 15 ms 24040 KB Output is correct
5 Correct 20 ms 24104 KB Output is correct
6 Correct 18 ms 23892 KB Output is correct
7 Correct 22 ms 24048 KB Output is correct
8 Correct 20 ms 24148 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 15 ms 23892 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 15 ms 23796 KB Output is correct
3 Correct 15 ms 23928 KB Output is correct
4 Correct 15 ms 24040 KB Output is correct
5 Correct 20 ms 24104 KB Output is correct
6 Correct 18 ms 23892 KB Output is correct
7 Correct 22 ms 24048 KB Output is correct
8 Correct 20 ms 24148 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 15 ms 23892 KB Output is correct
11 Correct 146 ms 34312 KB Output is correct
12 Correct 178 ms 35016 KB Output is correct
13 Correct 192 ms 36416 KB Output is correct
14 Correct 310 ms 39100 KB Output is correct
15 Correct 414 ms 40132 KB Output is correct
16 Correct 408 ms 46228 KB Output is correct
17 Correct 2255 ms 47664 KB Output is correct
18 Correct 2309 ms 47600 KB Output is correct
19 Correct 1933 ms 49444 KB Output is correct
20 Correct 140 ms 36204 KB Output is correct
21 Correct 170 ms 35932 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB Output is correct
2 Correct 15 ms 23796 KB Output is correct
3 Correct 15 ms 23928 KB Output is correct
4 Correct 15 ms 24040 KB Output is correct
5 Correct 20 ms 24104 KB Output is correct
6 Correct 18 ms 23892 KB Output is correct
7 Correct 22 ms 24048 KB Output is correct
8 Correct 20 ms 24148 KB Output is correct
9 Correct 15 ms 23892 KB Output is correct
10 Correct 15 ms 23892 KB Output is correct
11 Correct 146 ms 34312 KB Output is correct
12 Correct 178 ms 35016 KB Output is correct
13 Correct 192 ms 36416 KB Output is correct
14 Correct 310 ms 39100 KB Output is correct
15 Correct 414 ms 40132 KB Output is correct
16 Correct 408 ms 46228 KB Output is correct
17 Correct 2255 ms 47664 KB Output is correct
18 Correct 2309 ms 47600 KB Output is correct
19 Correct 1933 ms 49444 KB Output is correct
20 Correct 140 ms 36204 KB Output is correct
21 Correct 170 ms 35932 KB Output is correct
22 Execution timed out 3046 ms 50880 KB Time limit exceeded
23 Halted 0 ms 0 KB -