제출 #1083339

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1083339		Requiem	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	176 ms	53244 KiB

oneway

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

컴파일 시 표준 에러 (stderr) 메시지

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40