oj.uz

Submission #617745

# Submission time Handle Problem Language Result Execution time Memory
617745 2022-08-01T13:09:55 Z faruk One-Way Streets (CEOI17_oneway) C++17
0 / 100
 2 ms 468 KB 
#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<pii> > graph;
vector<int> disc;
vector<int> low;
vector<pii> par;
vector<bool> visited;

vector<bool> normal;
vector<bool> bridge;
vector<vector<pii> > tree;

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].first;
        int edgenum = graph[v][i].second;
        
        if (i != 0 && curr == graph[v][i - 1].first) {
            bridge[edgenum] = false;
            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, edgenum});
            tree[v].push_back({curr, edgenum});

            low[v] = min(low[v], low[curr]);
            if (low[curr] > disc[v])
                bridge[edgenum] = true;
        }
    }
}

void dfs2(int v, int p = -1) {
    for (pii x : tree[v]) {
        if (x.first != p)
        {
            par[x.first] = pii(v, x.second);
            dfs2(x.first, v);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    //freopen("fout.txt", "w", stdout);

    cin >> n >> m;
    graph.resize(n + 1, vector<pii>());
    visited.resize(n + 1, false);
    disc.resize(n + 1, 1e9);
    low.resize(n + 1, 1e9);
    normal.resize(m + 1, false);
    bridge.resize(m + 1, false);
    par.resize(n + 1, pii(-1, -1));
    tree.resize(n + 1, vector<pii>());

    for (int i = 0; i < m; i++) {
        int f, t;
        cin >> f >> t;
        if (f < t)
            normal[i] = true;
        graph[f].push_back({t, i});
        graph[t].push_back({f, i});
    }

    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; pii t(0, 0);
        cin >> f >> t.first;
        dfs2(f);
        par[f] = pii(-1, -1);
        pii s = par[t.first];
        while (s.first != -1) {
            if (bridge[s.second]) {
                if (normal[s.second]) {
                    if (s.first < t.first)
                        out[s.second] = 'R';
                    else
                        out[s.second] = 'L';
                }
                else {
                    if (s < t)
                        out[s.second] = 'L';
                    else
                        out[s.second] = 'R';
                }
            }
            pii temp = s;
            s = par[s.first];
            t = temp;
        }
    }

    cout << out << "\n";
}

Compilation message

oneway.cpp: In function 'void dfs(int, int)':
oneway.cpp:24: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]
   24 |     for (int i = 0; i < graph[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 320 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 2 ms 452 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Incorrect 1 ms 340 KB Output isn't correct
10 Halted 0 ms 0 KB -