oj.uz

답안 #644272

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
644272 2022-09-24T10:16:47 Z farmerboy One-Way Streets (CEOI17_oneway) C++17
100 / 100
 197 ms 46720 KB 
/*
    Template Version: 1.0.0 - 20220620
    Author: Nguyen Tan Bao
    Status:
    Idea:
*/

#include <bits/stdc++.h>
#define FI first
#define SE second
#define ALL(a) a.begin(), a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define TRAV(x, a) for (auto &x : a)

using namespace std;
using ll = long long; using ld = double; 
using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<ld, ld>;
using cd = complex<ld>; using vcd = vector<cd>;

using vi = vector<int>; using vl = vector<ll>;
using vd = vector<ld>; using vs = vector<string>;
using vpi = vector<pi>; using vpl = vector<pl>; using vpd = vector<pd>; // vector<pair>

template<class T> using min_pq = priority_queue<T, vector<T>, greater<T> >;
template<class T> inline int ckmin(T& a, const T& val) { return val < a ? a = val, 1 : 0; }
template<class T> inline int ckmax(T& a, const T& val) { return a < val ? a = val, 1 : 0; }
template<class T> void remDup(vector<T>& v) { sort(ALL(v)); v.erase(unique(ALL(v)), end(v)); }

constexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set
constexpr int bits(int x) { return x == 0 ? 0 : 31-__builtin_clz(x); } // floor(log2(x)) 
constexpr int p2(int x) { return 1<<x; }
constexpr int msk2(int x) { return p2(x)-1; }

ll ceilDiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
ll floorDiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down
void setPrec(int x) { cout << fixed << setprecision(x); }

// TO_STRING
#define ts to_string
string ts(char c) { return string(1, c); }
string ts(const char* s) { return (string) s; }
string ts(string s) { return s; }
string ts(bool b) { return (b ? "true" : "false"); }

template<class T> using V = vector<T>;
template<class T> string ts(complex<T> c);
string ts(V<bool> v);
template<size_t sz> string ts(bitset<sz> b);
template<class T> string ts(T v);
template<class T, class U> string ts(pair<T,U> p);
template<class ...U> string ts(tuple<U...> u);

template<class T> string ts(complex<T> c) { stringstream ss; ss << c; return ss.str(); }
string ts(V<bool> v) {string res = "{"; FOR(i,0,SZ(v)-1) res += char('0'+v[i]); res += "}"; return res; }
template<size_t sz> string ts(bitset<sz> b) { string res = ""; FOR(i,0,SZ(b)-1) res += char('0'+b[i]); return res; }
template<class T> string ts(T v) { // containers with begin(), end()
    bool fst = 1; string res = "";
    for (const auto& x: v) { if (!fst) res += " "; fst = 0; res += ts(x); }
    return res;
}
template<class T, class U> string ts(pair<T,U> p) { return "(" + ts(p.FI) + ", " + ts(p.SE) + ")"; }
template<size_t i, class T> string print_tuple_utils(const T& tup) { if constexpr(i == tuple_size<T>::value) return ")"; else return (i ? ", " : "(") + ts(get<i>(tup)) + print_tuple_utils<i + 1, T>(tup); }
template<class ...U> string ts(tuple<U...> u) { return print_tuple_utils<0, tuple<U...>>(u); }

// OUTPUT
template<class T> void pr(T x) { cout << ts(x); }
template<class T, class ...U> void pr(const T& t, const U&... u) { pr(t); pr(u...); }
void ps() { pr("\n"); } // print w/ spaces
template<class T, class ...U> void ps(const T& t, const U&... u) { pr(t); if (sizeof...(u)) pr(" "); ps(u...); }

// DEBUG
void DBG() { cerr << "]" << endl; }
template<class T, class ...U> void DBG(const T& t, const U&... u) { cerr << ts(t); if (sizeof...(u)) cerr << ", "; DBG(u...); }

#ifdef LOCAL_DEBUG
#define CONCAT(x, y) x##y
#define with_level setw(__db_level * 2) << setfill(' ') << "" << setw(0)
#define dbg(...) cerr << with_level << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define chk(...) if (!(__VA_ARGS__)) cerr << setw(__db_level * 2) << setfill(' ') << "" << setw(0) << "Line(" << __LINE__ << ") -> function(" << __FUNCTION__  << ") -> CHK FAILED: (" << #__VA_ARGS__ << ")" << "\n", exit(0);
#define db_block() debug_block CONCAT(dbbl, __LINE__)
int __db_level = 0;
struct debug_block {
    debug_block() { cerr << with_level << "{" << endl; ++__db_level; }
    ~debug_block() { --__db_level; cerr << with_level << "}" << endl; }
};
#else
#define dbg(...) 0
#define chk(...) 0
#define db_block() 0
#endif

const ld PI = acos(-1.0);
const int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
const ld EPS = 1e-9;
const ll MODBASE = 1000000007LL;
const int INF = 0x3f3f3f3f;

const int MAXN = 100010;
const int MAXM = 1000;
const int MAXK = 16;
const int MAXQ = 200010;

int n, m, level[MAXN], dp[MAXN], par[MAXN], cnt[MAXN];
int res[MAXN], newIdx[MAXN], N, head[MAXN];
vector<vi> a[MAXN], b[MAXN], edges2;
vpi edges;
bool visited[MAXN];

void dfs(int u, int p, int edgeIdx) {
    TRAV(pa, a[u]) {
        int v = pa[0];
        int idx = pa[1];
        int dir = pa[2];
        if (!level[v]) {
            level[v] = level[u] + 1;
            res[idx] = dir;
            dfs(v, u, idx);
            dp[u] += dp[v];
        } else {
            if (idx == edgeIdx) continue;
            res[idx] = 2;
            if (level[v] > level[u]) {
                // going down
                dp[u]--;
            } else {
                // going up
                dp[u]++;
            }
        }
    }

    if (p != 0 && dp[u] == 0) {
        res[edgeIdx] = -1;
    } else {
        res[edgeIdx] = 2;
    }
}

void dfs2(int u, int group) {
    newIdx[u] = group;
    TRAV(pa, a[u]) {
        int v = pa[0];
        int idx = pa[1];
        int dir = pa[2];
        if (res[idx] != 2) {
            continue;
        }
        if (!newIdx[v]) {
            dfs2(v, group);
        }
    }
}

void dfs3(int u, int h) {
    visited[u] = 1;
    head[u] = h;
    TRAV(pa, b[u]) {
        int v = pa[0];
        int idx = pa[1];
        int dir = pa[2];
        if (!visited[v]) {
            par[v] = u;
            dfs3(v, h);
            cnt[u] += cnt[v];
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n >> m;
    FOR(i,1,m) {
        int u, v;
        cin >> u >> v;
        a[u].push_back({v, i, 1});
        a[v].push_back({u, i, 0});
        edges.push_back({u, v});
        res[i] = ' ';
    }

    FOR(i,1,n) {
        if (!level[i]) {
            level[i] = 1;
            dfs(i, 0, -1);
        }
    }

    FOR(i,1,n)
        if (!newIdx[i]) {
            N++;
            dfs2(i, N);
        }
    
    FOR(i,0,m-1) {
        int u = edges[i].FI, v = edges[i].SE, cs = i + 1;
        u = newIdx[u];
        v = newIdx[v];
        if (u != v) {
            b[u].push_back({v, cs, 1});
            b[v].push_back({u, cs, 0});
            edges2.push_back({u, v, cs});
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        u = newIdx[u];
        v = newIdx[v];
        if (u != v) {
            cnt[u]++;
            cnt[v]--;
        }
    }

    FOR(i,1,N) {
        if (!visited[i]) {
            dfs3(i, i);
        }
    }

    FOR(i,0,SZ(edges2)-1) {
        int u = edges2[i][0], v = edges2[i][1], c = edges2[i][2];
        if (par[u] == v) {
            int l = cnt[u], r = cnt[head[u]] - cnt[u];
            if (l < 0) {
                res[c] = 0;
            } else if (r < 0) {
                res[c] = 1;
            } else {
                res[c] = 2;
            }
        } else {
            int l = cnt[v], r = cnt[head[v]] - cnt[v];
            if (l < 0) {
                res[c] = 1;
            } else if (r < 0) {
                res[c] = 0;
            } else {
                res[c] = 2;
            }
        }
    }

    FOR(i,1,m) {
        // cout << res[i] << "\n";
        if (res[i] == 2) cout << 'B';
        else if (res[i] == 1) cout << 'R';
        else cout << 'L';
    }
    return 0;
}

Compilation message

oneway.cpp: In function 'void dfs2(int, int)':
oneway.cpp:148:13: warning: unused variable 'dir' [-Wunused-variable]
  148 |         int dir = pa[2];
      |             ^~~
oneway.cpp: In function 'void dfs3(int, int)':
oneway.cpp:163:13: warning: unused variable 'idx' [-Wunused-variable]
  163 |         int idx = pa[1];
      |             ^~~
oneway.cpp:164:13: warning: unused variable 'dir' [-Wunused-variable]
  164 |         int dir = pa[2];
      |             ^~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5160 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5160 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 85 ms 22076 KB Output is correct
12 Correct 93 ms 22972 KB Output is correct
13 Correct 104 ms 24372 KB Output is correct
14 Correct 117 ms 28048 KB Output is correct
15 Correct 126 ms 29624 KB Output is correct
16 Correct 176 ms 40820 KB Output is correct
17 Correct 139 ms 42928 KB Output is correct
18 Correct 169 ms 40760 KB Output is correct
19 Correct 128 ms 44256 KB Output is correct
20 Correct 89 ms 22384 KB Output is correct
21 Correct 71 ms 22228 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 4 ms 5160 KB Output is correct
4 Correct 4 ms 5332 KB Output is correct
5 Correct 3 ms 5332 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 3 ms 5204 KB Output is correct
11 Correct 85 ms 22076 KB Output is correct
12 Correct 93 ms 22972 KB Output is correct
13 Correct 104 ms 24372 KB Output is correct
14 Correct 117 ms 28048 KB Output is correct
15 Correct 126 ms 29624 KB Output is correct
16 Correct 176 ms 40820 KB Output is correct
17 Correct 139 ms 42928 KB Output is correct
18 Correct 169 ms 40760 KB Output is correct
19 Correct 128 ms 44256 KB Output is correct
20 Correct 89 ms 22384 KB Output is correct
21 Correct 71 ms 22228 KB Output is correct
22 Correct 159 ms 42912 KB Output is correct
23 Correct 160 ms 40912 KB Output is correct
24 Correct 197 ms 40904 KB Output is correct
25 Correct 136 ms 46720 KB Output is correct
26 Correct 148 ms 42368 KB Output is correct
27 Correct 150 ms 41008 KB Output is correct
28 Correct 63 ms 19108 KB Output is correct
29 Correct 91 ms 21980 KB Output is correct
30 Correct 88 ms 22152 KB Output is correct
31 Correct 100 ms 22484 KB Output is correct
32 Correct 93 ms 30036 KB Output is correct