Submission #570842

#	Time	Username	Problem	Language	Result	Execution time	Memory
570842		vbee	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	2 ms	2772 KiB

oneway

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define ii pair<int,int>
#define vii vector<ii>
#define vi vector<int>
#define fi first
#define se second
#define TASK "onewaystreet"
#define ll long long
#define pll pair<ll, ll>
#define vll vector<ll>
#define vpll vector<pll>
#define pb push_back
#define MASK(i) (1 << (i))
#define BIT(x, i) ((x >> (i)) & 1)

using namespace std;

const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int N = 1e5 + 7;

map<pair<int, int>, int> M;
int n, m, p, num[N], low[N], cnt = 0;
vector<int> g[N];
bool visited[N];
string ans;
vector<pair<int, int> > edge;
void visit(int u, int p){
    low[u] = num[u] = ++cnt;
    for (auto v : g[u]) if (v != p) {
        if (num[v]) low[u] = min(low[u], num[v]);
        else {
            visit(v, u);
            low[u] = min(low[u], low[v]);
            if (low[v] >= num[v]) {
                if (M[{u, v}]){
                    if (ans[M[{u, v}]] != 'B')
                        edge.pb({u, v});
                }
                else if (M[{v, u}]) {
                    if (ans[M[{v, u}]] != 'B')
                        edge.pb({v, u});
                }
            }
        }
    }
}
map<pair<int, int>, int> M2;
bool dfs(int u, int x){
    visited[u] = true;
    bool flag = false;
    vector<pair<int, int>> candidate;
    queue<int> kew;
    kew.push(u);
    while (!kew.empty()){
        int k = kew.front();
        kew.pop();
        if (k == x) flag = true;
        for (auto v : g[k]) if (!visited[v]) {
            if (M2[{k, v}] || M2[{v, k}]) {
                candidate.pb({k, v});
                continue;
            }
            visited[v] = true;
            kew.push(v);
        }
    }
    if (flag) return true;
    sort(all(candidate));
    candidate.resize(unique(all(candidate)) - candidate.begin());
    for (auto v : candidate){
        if (dfs(v.se, x) == true){
            flag = true;
            if (M[{v.fi, v.se}])
                ans[M[{v.fi, v.se}]] = 'R';
            else if (M[{v.se, v.fi}])
                ans[M[{v.se, v.fi}]] = 'L';
        }
    }
    return flag;
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
//    freopen(TASK".inp", "r", stdin);
//    freopen(TASK".out", "w", stdout);
    //Nho tat file
    cin >> n >> m;
    ans.resize(m + 1);
    for (int i = 1; i <= m; i++){
        int u, v; cin >> u >> v;
        if (M[{u, v}] || M[{v, u}]){
            ans[i] = 'B';
        }
        else if (u == v) ans[i] = 'B';
        else {
            g[u].pb(v);
            g[v].pb(u);
        }
        M[{u, v}] = i;
    }
   for (int i = 1; i <= n; i++) if (num[i] == 0)
        visit(i, i);
    for (int i = 1; i <= m; i++) ans[i] = 'B';
    for (int i = 0; i < edge.size(); i++){
        int u = edge[i].fi, v = edge[i].se;
        ans[M[{u, v}]] = ' ';
        M2[{u, v}]++;
    }
    cin >> p;
    while (p--){
        int x, y; cin >> x >> y;
        memset(visited, false, sizeof visited);
        dfs(x, y);
    }
    for (int i = 1; i < ans.size(); i++) cout << ans[i];
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < edge.size(); i++){
      |                     ~~^~~~~~~~~~~~~
oneway.cpp:117:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     for (int i = 1; i < ans.size(); i++) cout << ans[i];
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40