oj.uz

답안 #886102

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886102 2023-12-11T13:09:48 Z Kutan One-Way Streets (CEOI17_oneway) C++14
100 / 100
 465 ms 36812 KB 
// Cao Quang Hung
#include <cassert>
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cwchar>
#include <cwctype>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>

using namespace std;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long , long long>
#define vi vector<int>
#define vpii vector<pii>
#define SZ(x) ((int)(x.size()))
#define fi first
#define se second
#define IN(x,y) ((y).find((x))!=(y).end())
#define ALL(t) t.begin(),t.end()
#define FOREACH(i,t) for (typeof(t.begin()) i=t.begin(); i!=t.end(); i++)
#define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
#define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
#define FOR(i, n) for (int (i) = 0; (i) < (n); ++(i))
#define dem(x) __builtin_popcount(x)
#define Mask(x) (1LL << (x))
#define BIT(x, i) ((x) >> (i) & 1)
#define ln '\n'
#define io_faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
///mt19937 rnd(time(0));

const int INF = 1e9 , mod = 1e9 + 7;

template <class T1, class T2>
inline T1 mul(T1& x, const T2 &k){ return x = (1LL * x * k) % mod; }

template <class T1 , class T2>
inline T1 pw(T1 x, T2 k){T1 res = 1; for (; k ; k >>= 1){ if (k & 1) mul(res, x); mul(x, x); } return res;}

template <class T>
inline bool minimize(T &x, const T &y){ if (x > y){x = y; return 1;} return 0; }

template <class T>
inline bool maximize(T &x, const T &y){ if (x < y){x = y; return 1;} return 0; }

template <class T>
inline void add(T &x , const T &y){ if ((x += y) >= mod) x -= mod; }

template <class T>
inline T product (const T &x , const T &y) { return 1LL * x * y % mod; }

#define PROB "a"
void file(){
    if(fopen(PROB".inp", "r")){
        freopen(PROB".inp","r",stdin);
        freopen(PROB".out","w",stdout);
    }
}
void sinh_(){
//    srand(time(0));
//    freopen(PROB".inp" , "w" , stdout);
//    int n;
}

typedef long long ll;
typedef double db;
const int N = 1e5 + 5;

int n, m, q;
pii edge[N], ans[N];
vi adj[N];
vpii g[N];

int num[N], low[N], timeDfs = 0;
int numScc = 0, comp[N]; vector<int> scc[N];
int par[N][17], depth[N] = {}, edge_id[N];
bool oke[N], used[N], vis[N];

int other(int x, int id) {
    return x ^ edge[id].fi ^ edge[id].se;
}

void readip(){
    cin >> n >> m;
    REP(i, 1, m) {
        int u, v; cin >> u >> v;
        adj[u].eb(i);
        adj[v].eb(i);
        edge[i] = {u, v};
    }
}

vector<int> st;
void dfs(int u) {
    st.eb(u);
    num[u] = low[u] = ++timeDfs;
    for (const auto &id : adj[u]) if (!used[id]) {
        used[id] = true;
        int v = other(u, id);
        if (num[v]) minimize(low[u], num[v]);
        else {
            dfs(v);
            minimize(low[u], low[v]);
        }
    }
    if (num[u] == low[u]) {
        ++numScc;
        int x;
        do {
            x = st.back();
            st.pop_back();
            comp[x] = numScc;
            scc[numScc].eb(x);
        } while(x != u);
    }
}

void dfs_tree(int u, int p) {
    vis[u] = true;
    for (const auto &[v, id] : g[u]) if (v != p) {
        edge_id[v] = id;
        depth[v] = depth[u] + 1;
        par[v][0] = u;
        REP(i, 1, 16) par[v][i] = par[par[v][i - 1]][i - 1];
        dfs_tree(v, u);
    }
}

int Lca(int u, int v) {
    if (depth[u] > depth[v]) swap(u, v);
    int dif = depth[v] - depth[u];
    REP(i, 0, 16) if (BIT(dif, i)) v = par[v][i];
    if (u == v) return u;
    REPD(i, 16, 0) if (par[v][i] != par[u][i])
        u = par[u][i] , v = par[v][i];
    return par[u][0];
}

struct query{
    int u, v;
    query(int _u = 0, int _v = 0) {
        u = _u, v = _v;
    }
    bool operator < (const query &other) const {
        return depth[Lca(u, v)] < depth[Lca(other.u, other.v)];
    }
} Query[N];

#define UP 1
#define DOWN 2

void direct(int u, int anc, int d) {
    while(u != anc) {
        int Par = par[u][0];
        int nid = edge_id[u];
        
        if (oke[nid]) return;
        oke[nid] = true;

        ans[nid] = edge[nid];
        if (d == UP) {
            // u -> Par
            if (comp[ans[nid].first] != u)
                swap(ans[nid].first, ans[nid].second);
        }
        else {
            // Par -> u;
            if (comp[ans[nid].first] != Par)
                swap(ans[nid].first, ans[nid].second);
        }
        u = Par;
    }
} 

void solve(){           
    REP(i, 1, n) if (!num[i]) dfs(i);
    REP(i, 1, numScc) {
        for (int u : scc[i]) for (int id : adj[u]) {
            int v = other(u, id);
            if (comp[v] == i) continue;
            g[i].eb(comp[v], id);
        }
    }   
    REP(i, 1, numScc) if (!vis[i]) 
        dfs_tree(i, -1);
    cin >> q;
    REP(i, 1, q) {
        cin >> Query[i].u >> Query[i].v;
        Query[i].u = comp[Query[i].u];
        Query[i].v = comp[Query[i].v];
    }
    sort(Query + 1, Query + q + 1);
    REP(i, 1, q) {
        int lca = Lca(Query[i].u, Query[i].v);
        direct(Query[i].u, lca, UP);
        direct(Query[i].v, lca, DOWN);
    }

    REP(i, 1, m) {
        if (!oke[i]) cout << "B";
        else if (edge[i] == ans[i]) cout << "R";
        else cout << "L";
    }
}   

int main(){
    sinh_();
    io_faster
    file();
    int t = 1;
//    cin >> t;
    while (t--){
        readip();
        solve();
    }
}

Compilation message

oneway.cpp: In function 'void readip()':
oneway.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
oneway.cpp:155:5: note: in expansion of macro 'REP'
  155 |     REP(i, 1, m) {
      |     ^~~
oneway.cpp: In function 'void dfs_tree(int, int)':
oneway.cpp:190:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  190 |     for (const auto &[v, id] : g[u]) if (v != p) {
      |                      ^
oneway.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
oneway.cpp:194:9: note: in expansion of macro 'REP'
  194 |         REP(i, 1, 16) par[v][i] = par[par[v][i - 1]][i - 1];
      |         ^~~
oneway.cpp: In function 'int Lca(int, int)':
oneway.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
oneway.cpp:202:5: note: in expansion of macro 'REP'
  202 |     REP(i, 0, 16) if (BIT(dif, i)) v = par[v][i];
      |     ^~~
oneway.cpp:93:29: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   93 | #define REPD(i,a,b) for(int (i)=(a); (i)>=(b);--i)
      |                             ^
oneway.cpp:204:5: note: in expansion of macro 'REPD'
  204 |     REPD(i, 16, 0) if (par[v][i] != par[u][i])
      |     ^~~~
oneway.cpp: In function 'void solve()':
oneway.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
oneway.cpp:246:5: note: in expansion of macro 'REP'
  246 |     REP(i, 1, n) if (!num[i]) dfs(i);
      |     ^~~
oneway.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
oneway.cpp:247:5: note: in expansion of macro 'REP'
  247 |     REP(i, 1, numScc) {
      |     ^~~
oneway.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
oneway.cpp:254:5: note: in expansion of macro 'REP'
  254 |     REP(i, 1, numScc) if (!vis[i])
      |     ^~~
oneway.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
oneway.cpp:257:5: note: in expansion of macro 'REP'
  257 |     REP(i, 1, q) {
      |     ^~~
oneway.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
oneway.cpp:263:5: note: in expansion of macro 'REP'
  263 |     REP(i, 1, q) {
      |     ^~~
oneway.cpp:92:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   92 | #define REP(i,a,b) for(int (i)=(a);(i)<=(b);++i)
      |                            ^
oneway.cpp:269:5: note: in expansion of macro 'REP'
  269 |     REP(i, 1, m) {
      |     ^~~
oneway.cpp: In function 'void file()':
oneway.cpp:125:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  125 |         freopen(PROB".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:126:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         freopen(PROB".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 11040 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11048 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11096 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 11040 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11048 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11096 KB Output is correct
11 Correct 26 ms 16220 KB Output is correct
12 Correct 29 ms 17236 KB Output is correct
13 Correct 32 ms 18428 KB Output is correct
14 Correct 40 ms 22736 KB Output is correct
15 Correct 42 ms 25428 KB Output is correct
16 Correct 53 ms 29268 KB Output is correct
17 Correct 53 ms 31856 KB Output is correct
18 Correct 54 ms 29760 KB Output is correct
19 Correct 55 ms 33276 KB Output is correct
20 Correct 29 ms 16976 KB Output is correct
21 Correct 28 ms 17364 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 11040 KB Output is correct
3 Correct 2 ms 11100 KB Output is correct
4 Correct 3 ms 11100 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 2 ms 11100 KB Output is correct
8 Correct 2 ms 11048 KB Output is correct
9 Correct 2 ms 11100 KB Output is correct
10 Correct 2 ms 11096 KB Output is correct
11 Correct 26 ms 16220 KB Output is correct
12 Correct 29 ms 17236 KB Output is correct
13 Correct 32 ms 18428 KB Output is correct
14 Correct 40 ms 22736 KB Output is correct
15 Correct 42 ms 25428 KB Output is correct
16 Correct 53 ms 29268 KB Output is correct
17 Correct 53 ms 31856 KB Output is correct
18 Correct 54 ms 29760 KB Output is correct
19 Correct 55 ms 33276 KB Output is correct
20 Correct 29 ms 16976 KB Output is correct
21 Correct 28 ms 17364 KB Output is correct
22 Correct 465 ms 33032 KB Output is correct
23 Correct 340 ms 31064 KB Output is correct
24 Correct 234 ms 31128 KB Output is correct
25 Correct 309 ms 36812 KB Output is correct
26 Correct 321 ms 32592 KB Output is correct
27 Correct 316 ms 31144 KB Output is correct
28 Correct 53 ms 14164 KB Output is correct
29 Correct 87 ms 17492 KB Output is correct
30 Correct 113 ms 17904 KB Output is correct
31 Correct 74 ms 18124 KB Output is correct
32 Correct 229 ms 24752 KB Output is correct