Submission #617692

#	Time	Username	Problem	Language	Result	Execution time	Memory
617692		faruk	One-Way Streets (CEOI17_oneway)	C++17	30 / 100	3094 ms	29476 KiB

oneway

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define ld long double
 
using namespace std;
 
int n, m;
vector<vector<int> > graph;
vector<int> disc;
vector<int> low;
vector<int> par;
vector<bool> visited;
 
vector<vector<int> > tree;
 
set<pii> bridges;
int timer = 0;
void dfs(int v, int p = -1) {
    visited[v] = true;
    disc[v] = low[v] = timer++;
    sort(graph[v].begin(), graph[v].end());
    for (int i = 0; i < graph[v].size(); i++) {
        int curr = graph[v][i];
        
        if (i != 0 && curr == graph[v][i - 1]) {
            bridges.erase(minmax(v, curr));
            continue;
        }
 
        if (curr == p)
            continue;
        else if (visited[curr])
            low[v] = min(low[v], disc[curr]);
        else {
            dfs(curr, v);
 
            tree[curr].push_back(v);
            tree[v].push_back(curr);
 
            low[v] = min(low[v], low[curr]);
            if (low[curr] > disc[v])
                bridges.insert(minmax(v, curr));
        }
    }
}
 
void dfs2(int v, int p = -1) {
    par[v] = p;
    for (int x : tree[v]) {
        if (x != p)
            dfs2(x, v);
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    graph.resize(n + 1, vector<int>());
    visited.resize(n + 1, false);
    disc.resize(n + 1, 1e9);
    low.resize(n + 1, 1e9);
    par.resize(n + 1, -1);
    tree.resize(n + 1, vector<int>());
 
    map<pii, int> edges;
    set<pii> normal;
    for (int i = 0; i < m; i++) {
        int f, t;
        cin >> f >> t;
        if (f < t)
            normal.insert(pii(f, t));
        edges[minmax(f, t)] = i;
        graph[f].push_back(t);
        graph[t].push_back(f);
    }
 
    for (int i = 1; i <= n; i++) {
        if (!visited[i])
            dfs(i); 
    }
 
    string out = "";
    for (int i = 0; i < m; i++)
        out += 'B';
    
    int p;
    cin >> p;
    while (p--) {
        int f, t;
        cin >> f >> t;
        dfs2(f);
        int s = par[t];
        while (s != -1) {
            if (bridges.count(minmax(s, t))) {
                if (normal.count(minmax(s, t))) {
                    if (s < t)
                        out[edges[minmax(s, t)]] = 'R';
                    else
                        out[edges[minmax(s, t)]] = 'L';
                }
                else {
                    if (s < t)
                        out[edges[minmax(s, t)]] = 'L';
                    else
                        out[edges[minmax(s, t)]] = 'R';
                }
            }
            int temp = s;
            s = par[s];
            t = temp;
        }
    }
 
    cout << out << "\n";
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:23:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for (int i = 0; i < graph[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~

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