oj.uz

Submission #617692

# Submission time Handle Problem Language Result Execution time Memory
617692 2022-08-01T12:51:35 Z faruk One-Way Streets (CEOI17_oneway) C++17
30 / 100
 3000 ms 29476 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<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

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.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 8 ms 596 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 6 ms 584 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 8 ms 596 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 6 ms 584 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 161 ms 14900 KB Output is correct
12 Correct 316 ms 17108 KB Output is correct
13 Correct 368 ms 20224 KB Output is correct
14 Correct 701 ms 24108 KB Output is correct
15 Correct 636 ms 25260 KB Output is correct
16 Correct 235 ms 27416 KB Output is correct
17 Execution timed out 3094 ms 29476 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 8 ms 596 KB Output is correct
6 Correct 1 ms 456 KB Output is correct
7 Correct 6 ms 584 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 2 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 161 ms 14900 KB Output is correct
12 Correct 316 ms 17108 KB Output is correct
13 Correct 368 ms 20224 KB Output is correct
14 Correct 701 ms 24108 KB Output is correct
15 Correct 636 ms 25260 KB Output is correct
16 Correct 235 ms 27416 KB Output is correct
17 Execution timed out 3094 ms 29476 KB Time limit exceeded
18 Halted 0 ms 0 KB -