oj.uz

Submission #644273

# Submission time Handle Problem Language Result Execution time Memory
644273 2022-09-24T10:17:42 Z farmerboy One-Way Streets (CEOI17_oneway) C++17
100 / 100
 183 ms 45364 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;
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;
    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[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[v];
            if (l < 0) {
                res[c] = 1;
            } else if (r < 0) {
                res[c] = 0;
            } else {
                res[c] = 2;
            }
        }
    }

    FOR(i,1,m) {
        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:162:13: warning: unused variable 'idx' [-Wunused-variable]
  162 |         int idx = pa[1];
      |             ^~~
oneway.cpp:163:13: warning: unused variable 'dir' [-Wunused-variable]
  163 |         int dir = pa[2];
      |             ^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5332 KB Output is correct
8 Correct 3 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

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5332 KB Output is correct
8 Correct 3 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 87 ms 21092 KB Output is correct
12 Correct 101 ms 22080 KB Output is correct
13 Correct 106 ms 23376 KB Output is correct
14 Correct 125 ms 26848 KB Output is correct
15 Correct 116 ms 28380 KB Output is correct
16 Correct 166 ms 39372 KB Output is correct
17 Correct 138 ms 41492 KB Output is correct
18 Correct 168 ms 39344 KB Output is correct
19 Correct 123 ms 42808 KB Output is correct
20 Correct 83 ms 21420 KB Output is correct
21 Correct 79 ms 21176 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 2 ms 4948 KB Output is correct
3 Correct 3 ms 5204 KB Output is correct
4 Correct 3 ms 5332 KB Output is correct
5 Correct 4 ms 5332 KB Output is correct
6 Correct 3 ms 5204 KB Output is correct
7 Correct 3 ms 5332 KB Output is correct
8 Correct 3 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 87 ms 21092 KB Output is correct
12 Correct 101 ms 22080 KB Output is correct
13 Correct 106 ms 23376 KB Output is correct
14 Correct 125 ms 26848 KB Output is correct
15 Correct 116 ms 28380 KB Output is correct
16 Correct 166 ms 39372 KB Output is correct
17 Correct 138 ms 41492 KB Output is correct
18 Correct 168 ms 39344 KB Output is correct
19 Correct 123 ms 42808 KB Output is correct
20 Correct 83 ms 21420 KB Output is correct
21 Correct 79 ms 21176 KB Output is correct
22 Correct 149 ms 41432 KB Output is correct
23 Correct 160 ms 39548 KB Output is correct
24 Correct 183 ms 39480 KB Output is correct
25 Correct 134 ms 45364 KB Output is correct
26 Correct 144 ms 41000 KB Output is correct
27 Correct 147 ms 39708 KB Output is correct
28 Correct 61 ms 18108 KB Output is correct
29 Correct 99 ms 20956 KB Output is correct
30 Correct 84 ms 21164 KB Output is correct
31 Correct 95 ms 21620 KB Output is correct
32 Correct 90 ms 28964 KB Output is correct