oj.uz

Submission #1083339

# Submission time Handle Problem Language Result Execution time Memory
1083339 2024-09-03T02:22:02 Z Requiem One-Way Streets (CEOI17_oneway) C++17
100 / 100
 176 ms 53244 KB 
#include<bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define fi first
#define se second
#define ii pair<int, int>
#define iii pair<int, ii>
#define endl '\n'
#define pb push_back
#define fast ios_base::sync_with_stdio(NULL), cin.tie(NULL), cout.tie(NULL)
#define TASKNAME "oneway"
using namespace std;

/**
oneWay:
Cho 1 đồ thị n đỉnh m cạnh.
Ta có q cặp đỉnh.
Ta cần định hướng đồ thị sao cho từ xi có thể đi đến yi.

Ta cần xuất ra 1 xâu m kí tự gồm 'L', 'R', 'B':
L: trong mọi cách định hướng có thể, cạnh i đều phải hướng từ ai sang bi.
R: trong mọi cách định hướng có thể, cạnh i đều phải được định hướng từ bi sang ai.
B: nếu tồn tại cả hai trường hợp.

Nhận xét: Với 2-edge connected component (ko có cầu) thì ta luôn có 1 cách định hướng
để nó trở thành liên thông mạnh. Và khi đảo ngược cạnh lại thì nó sẽ vẫn là thành
phần liên thông cạnh.

Bây giờ ta đưa nó về thành cây khi rút gọn các 2-edge connected component thành 1 đỉnh.
Khi cập nhật cặp đỉnh x và y thì ta duyệt qua các cạnh của cái cây. Ta sẽ định
hướng nó từ trái qua phải. Cập nhật cái này thì ta phải cập nhật chỉ số.

Vì nó luôn tồn tại nghiệm nên ta không quan tâm là cách làm của ta có đúng hay không.
với những cạnh cầu không được định hướng thì sao cũng được.
**/

template<typename T> bool maximize (T &a, T b){  if (a < b) { a = b; return true; } return false; }
template<typename T> bool minimize (T &a, T b){  if (a > b) { a= b; return true; } return false; }
const int MAXN = 3e5 + 9;
int n, m, q;
ii edge[MAXN];
ii P[MAXN];
char answer[MAXN];


vector<vector<int>> g;
vector<vector<int>> bridgeTree;
vector<vector<int>> BinaryJumping;

struct dsu{
    vector<int> lab;
    dsu(int sz = 0){
        lab.resize(sz + 9, -1);
    }

    int root(int u){
        return ((lab[u] < 0) ? u : lab[u] = root(lab[u]));
    }

    void unite(int u, int v){
        u = root(u);
        v = root(v);
        if (u != v){
            if (lab[u] > lab[v]) swap(u, v);
            lab[u] += lab[v];
            lab[v] = u;
        }
    }
};
namespace subtask1{
    bool check(){
        return n <= 10 and m <= 20;
    }
    bool canLeft[21], canRight[21];
    bitset<21> reachbability[21];
    int state[21];

    bool checkReachability(){
        FOR(i, 1, n){
            reachbability[i].reset();
        }
        FOR(i, 1, m){
            if (state[i] == 0) reachbability[edge[i].se][edge[i].fi] = 1;
            else reachbability[edge[i].fi][edge[i].se] = 1;
        }
        FOR(k, 1, n){
            FOR(i, 1, n){
                if (reachbability[i][k] == 1) reachbability[i] |= reachbability[k];
            }
        }

        FOR(i, 1, q){
            if (reachbability[P[i].fi][P[i].se] == 0) return false;
        }
        return true;
    }
    void backtrack(int pos){
        if (pos == m + 1){
            if (checkReachability()){
                FOR(j, 1, m){
                    if (state[j] == 0) canLeft[j] = 1;
                    else if (state[j] == 1) canRight[j] = 1;
                }
            }
            return;
        }

        backtrack(pos + 1);
        state[pos] = 1;
        backtrack(pos + 1);
        state[pos] = 0;
    }

    void solve(){
        backtrack(1);
        memset(canLeft, false, sizeof(canLeft));
        memset(canRight, false, sizeof(canRight));
        FOR(i, 1, m){
            if (canLeft[i] and canRight[i]) printf("B");
            else if (canLeft[i]) printf("L");
            else printf("R");
        }
    }
}

namespace subtask2{
    bool check(){
        return true;
    }

    vector<int> listBridge;
    int num[MAXN], low[MAXN], idComponent[MAXN], numcmp = 0, timeDfs = 0;
    int par[MAXN], depth[MAXN];
    bool used[MAXN], isBridge[MAXN], vis[MAXN];
    dsu DSU;

    void tarjan(vector<vector<int>> &g, int u){
        num[u] = low[u] = ++timeDfs;
        for(int id: g[u]){
            int v = edge[id].fi + edge[id].se - u;
            if (used[id]) continue;
            used[id] = true;
            if (!num[v]){
                tarjan(g, v);
                if (low[v] == num[v]) {
                    listBridge.pb(id);
                    isBridge[id] = true;
                }
                minimize(low[u], low[v]);
            }
            else{
                minimize(low[u], num[v]);
            }
        }
    }

    void dfs(vector<vector<int>> &g, int u, int p, bool fixed){
        if (fixed) idComponent[u] = numcmp;
        BinaryJumping[0][u] = p;
        vis[u] = true;
        for(auto id: g[u]){
            int v = edge[id].fi + edge[id].se - u;
            if (!vis[v] and !isBridge[id]) {
                depth[v] = depth[u] + 1;
                par[v] = id;
                dfs(g, v, u, fixed);
            }
        }
    }

    int getLCA(int u, int v){  //can phai test voi do cao lon
        if (depth[u] < depth[v]) swap(u, v);
        FORD(i, 20, 0){
             if (BinaryJumping[i][u] != -1 and depth[BinaryJumping[i][u]] >= depth[v]){
                 u = BinaryJumping[i][u];
             }
        }
        if (u == v) return u;
        FORD(i, 20, 0){
             if (BinaryJumping[i][u] != -1 and BinaryJumping[i][v] != -1 and BinaryJumping[i][u] != BinaryJumping[i][v]){
                 u = BinaryJumping[i][u];
                 v = BinaryJumping[i][v];
             }
        }
        return BinaryJumping[0][u];
    }

    void go(int u, int acs, bool up){
         while(depth[u] > depth[acs]){
               u = DSU.root(u);
               if (depth[u] <= depth[acs]) return;
               int edgeParent = par[u];
               if (up) answer[edgeParent] = ((u == edge[edgeParent].fi) ? 'R' : 'L');
               else answer[edgeParent] = ((u == edge[edgeParent].fi) ? 'L' : 'R');
               int v = edge[edgeParent].fi + edge[edgeParent].se - u;
               DSU.lab[u] = v;
         }
    }
    void orientation(){
        FOR(i, 1, q){
            int u = idComponent[P[i].fi];
            int v = idComponent[P[i].se];
            if (u == v) continue;
            int acs = getLCA(u, v);

            go(u, acs, 1);
            go(v, acs, 0);
        }
    }
    void solve(){
        memset(used, false, sizeof(used));
        memset(isBridge, false, sizeof(isBridge));
        memset(vis, false, sizeof(vis));
        DSU = dsu(n);
        BinaryJumping.resize(30, vector<int>(n + 9, -1));
        bridgeTree.resize(n + 9);
        FOR(i, 1, n){
            if (!num[i]) tarjan(g, i);
        }
//
        FOR(i, 1, n){
            if (!vis[i]) {
                numcmp++;
                dfs(g, i, -1, 1);
            }
        }
        FOR(i, 1, m){
            answer[i] = ' ';
            if (!isBridge[i]) answer[i] = 'B';
        }

        FOR(i, 0, (int) listBridge.size() - 1){  //xay bridge tree.
            int id = listBridge[i];
            int u = idComponent[edge[id].fi];
            int v = idComponent[edge[id].se];
            bridgeTree[u].pb(id);
            bridgeTree[v].pb(id);
            isBridge[id] = false;
            edge[id] = {u, v};
        }
        memset(vis, false, sizeof(vis));

        FOR(i, 1, numcmp){ //duyet cay bridge tree de xay lca.
            if (vis[i] == 0) {
                dfs(bridgeTree, i, -1, 0);
            }
        }

        FOR(i, 1, 20){
            FOR(j, 1, numcmp){
                if (BinaryJumping[i - 1][j] == -1) BinaryJumping[i][j] = -1;
                else BinaryJumping[i][j] = BinaryJumping[i - 1][BinaryJumping[i - 1][j]];
            }
        }
        orientation();
        FOR(i, 1, m){
            if (answer[i] == ' ') printf("B");
            else printf("%c", answer[i]);
        }
    }
}
main(){
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> n >> m;
    g.resize(n + 10);
    FOR(i, 1, m){
        int u, v;
        cin >> u >> v;
        edge[i] = {u, v};
        g[u].pb(i);
        g[v].pb(i);
    }
    cin >> q;
    FOR(i, 1, q){
        cin >> P[i].fi >> P[i].se;
    }

//    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask2::check()) return subtask2::solve(), 0;
}

Compilation message

oneway.cpp:263:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  263 | main(){
      | ^~~~
oneway.cpp: In function 'int main()':
oneway.cpp:266:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  266 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:267:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  267 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

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

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 43 ms 14256 KB Output is correct
12 Correct 39 ms 19188 KB Output is correct
13 Correct 70 ms 26568 KB Output is correct
14 Correct 93 ms 37500 KB Output is correct
15 Correct 73 ms 41104 KB Output is correct
16 Correct 73 ms 45376 KB Output is correct
17 Correct 71 ms 47168 KB Output is correct
18 Correct 84 ms 45332 KB Output is correct
19 Correct 70 ms 48448 KB Output is correct
20 Correct 39 ms 25036 KB Output is correct
21 Correct 42 ms 24776 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1372 KB Output is correct
2 Correct 1 ms 1372 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Correct 1 ms 1628 KB Output is correct
9 Correct 1 ms 1628 KB Output is correct
10 Correct 1 ms 1628 KB Output is correct
11 Correct 43 ms 14256 KB Output is correct
12 Correct 39 ms 19188 KB Output is correct
13 Correct 70 ms 26568 KB Output is correct
14 Correct 93 ms 37500 KB Output is correct
15 Correct 73 ms 41104 KB Output is correct
16 Correct 73 ms 45376 KB Output is correct
17 Correct 71 ms 47168 KB Output is correct
18 Correct 84 ms 45332 KB Output is correct
19 Correct 70 ms 48448 KB Output is correct
20 Correct 39 ms 25036 KB Output is correct
21 Correct 42 ms 24776 KB Output is correct
22 Correct 176 ms 49728 KB Output is correct
23 Correct 160 ms 47972 KB Output is correct
24 Correct 132 ms 48192 KB Output is correct
25 Correct 160 ms 53244 KB Output is correct
26 Correct 166 ms 49472 KB Output is correct
27 Correct 165 ms 48036 KB Output is correct
28 Correct 24 ms 7764 KB Output is correct
29 Correct 58 ms 27160 KB Output is correct
30 Correct 57 ms 27336 KB Output is correct
31 Correct 49 ms 27592 KB Output is correct
32 Correct 92 ms 35672 KB Output is correct