oj.uz

Submission #1005944

# Submission time Handle Problem Language Result Execution time Memory
1005944 2024-06-23T08:37:37 Z serifefedartar One-Way Streets (CEOI17_oneway) C++17
0 / 100
 3000 ms 860 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 1e9 + 7;
const ll MAXN = 1e5 + 100;
 
vector<vector<int>> graph, G, G2, G_rev;
int mark[MAXN], a[MAXN], b[MAXN], vis[MAXN], par[MAXN], sz[MAXN], ways[MAXN];
 
void dfs(int node, int parent) {
    vis[node] = 1;
    for (auto u : graph[node]) {
        if (u != parent && vis[u] != 2) {
            G[node].push_back(u);
            G_rev[u].push_back(node);
        }
        if (!vis[u])
            dfs(u, node);
    }
    vis[node] = 2;
}
 
int find(int node) {
    if (node == par[node])
        return node;
    return par[node] = find(par[node]);
}
 
void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b)
        return ;
    if (sz[b] > sz[a])
        swap(a, b);
    par[b] = a;
    sz[a] += sz[b];
}
 
stack<int> nds;
void dfs2(int node) {
    vis[node] = true;
    for (auto u : G[node]) {
        if (vis[u] == 0)
            dfs2(u);
    }
    nds.push(node);
}
 
void dfs3(int node) {
    vis[node] = true;
    for (auto u : G_rev[node]) {
        if (vis[u])
            continue;
        unite(node, u);
        dfs3(u);
    }
}
 
map<pair<int,int>,int> mp;
void dfs4(int node, int parent) {
    vis[node] = true;
    for (auto u : G2[node]) {
        if (u == parent)
            continue;
        dfs4(u, node);
        mark[node] += mark[u];
        if (mark[u] > 0) { // edge : u -> node
            if (mp[{u, node}] == 0)
                ways[mp[{node, u}]] = 1;
            else
                ways[mp[{u, node}]] = 2;
        } else if (mark[u] < 0) { // edge : node -> u
            if (mp[{u, node}] == 0)
                ways[mp[{node, u}]] = 2;
            else
                ways[mp[{u, node}]] = 1;
        }
    }
}

int main() {
    fast
    int n, m, q;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
        par[i] = i, sz[i] = 1;
    graph = vector<vector<int>>(n+1, vector<int>());
    G = vector<vector<int>>(n+1, vector<int>());
    G2 = vector<vector<int>>(n+1, vector<int>());
    G_rev = vector<vector<int>>(n+1, vector<int>());
    for (int i = 1; i <= m; i++) {
        cin >> a[i] >> b[i];
        graph[a[i]].push_back(b[i]);
        graph[b[i]].push_back(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        if (!vis[i])
            dfs(i, i);
    }
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    for (int i = 1; i <= n; i++) {
        if (!vis[i])
            dfs2(i);
    }
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    while (nds.size()) {
        int node = nds.top();
        nds.pop();
        if (!vis[node])
            dfs3(node);
    }
    for (int i = 1; i <= m; i++) {
        if (find(a[i]) != find(b[i]))
            mp[{find(a[i]), find(b[i])}] = i;
    }
 
    for (int i = 1; i <= m; i++) {
        if (find(a[i]) == find(b[i]))
            ways[i] = -1;
        else {
            G2[find(a[i])].push_back(find(b[i]));
            G2[find(b[i])].push_back(find(a[i]));
        }
    }

    cin >> q;
    while (q--) {
        int a, b;
        cin >> a >> b;
        a = find(a);
        b = find(b);
        if (a == b)
            continue;
 
        mark[b] -= 1;
        mark[a] += 1;
    }

    for (int i = 1; i <= n; i++)
        vis[i] = false;
    for (int i = 1; i <= n; i++) {
        if (!vis[find(i)])
            dfs4(find(i), find(i));
    }
    
    for (int i = 1; i <= m; i++) {
        if (ways[i] == -1)
            cout << "B";
        else if (ways[i] == 1)
            cout << "L";
        else if (ways[i] == 2)
            cout << "R";
        else
            cout << "B";
    }
    cout << "\n";
}

Subtask #1
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Execution timed out 3069 ms 600 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Execution timed out 3069 ms 600 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 464 KB Output is correct
2 Correct 1 ms 476 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Execution timed out 3069 ms 600 KB Time limit exceeded
7 Halted 0 ms 0 KB -