oj.uz

Submission #1027518

# Submission time Handle Problem Language Result Execution time Memory
1027518 2024-07-19T07:12:52 Z vjudge1 One-Way Streets (CEOI17_oneway) C++17
100 / 100
 559 ms 116808 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}
 
const int NM = 1e6 + 5;
const int mod = 1e6 + 3;
const int inf = 1e9 + 1;

vector<int> g[NM];
vector<pair<int, pair<int, int>>> G[NM];
int n, m, N, tin[NM], low[NM], timer, comp[NM];
pair<int, int> e[NM];
map<pair<int, int>, bool> is_cau, ditme, deophaicau;
map<pair<int, int>, int> val;

void dfs(int u, int p)
{
    tin[u] = low[u] = ++timer;
    for (int v : g[u]) 
        if (v != p)
        {
            if (tin[v])
                setmin(low[u], low[v]);
            else
            {
                dfs(v, u);
                if (low[v] > tin[u] && !deophaicau[{u, v}])
                    is_cau[{u, v}] = 1;
                setmin(low[u], low[v]);
            }
        }
}

bool vis[NM];

void cpr(int u)
{
    comp[u] = N;
    for (auto v : g[u]) 
    {
        if (is_cau[{u, v}] || is_cau[{v, u}])
        {
            if (comp[v])
            {
                G[N].push_back({comp[v], {u, v}});
                G[comp[v]].push_back({N, {v, u}});
            }
            continue;
        }
        if (comp[v])
            continue;
        cpr(v);
    }
}

void prep()
{
    for (int i = 1; i <= n; i++)
        if (!tin[i])
            dfs(i, 0);
    for (int i = 1; i <= n; i++)
        if (!comp[i])
        {
            ++N;
            cpr(i);
        }
}

int dp[NM], cur;

void DFS(int u)
{
    vis[u] = 1;
    for (auto v : G[u])
        if (!vis[v.fi])
        {
            DFS(v.fi);
            val[v.se] = dp[v.fi];
            dp[u] += dp[v.fi];
        }
}

pair<int, int> rev(pair<int, int> x)
{
    return {x.se, x.fi};
}

signed main()
{
    if (fopen("in.txt", "r")) {
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
    }
    fastIO
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int u, v;
        cin >> u >> v;
        e[i] = {u, v};
        if (ditme[{u, v}] || ditme[{v, u}])
        {
            deophaicau[{u, v}] = deophaicau[{v, u}] = true;
            continue;
        }
        ditme[{u, v}] = true;
        ditme[{v, u}] = true;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    prep();
    int q;
    cin >> q;
    while (q--)
    {
        int u, v;
        cin >> u >> v;
        dp[comp[u]]++;
        dp[comp[v]]--;
    }
    for (int i = 1; i <= N; i++)
        if (!vis[i])
            DFS(i);
    for (int i = 1; i <= m; i++)
    {
        if (!val[e[i]] && !val[rev(e[i])])
            cout << 'B';
        else if (val[e[i]] < 0 || val[rev(e[i])] > 0)
            cout << 'R';
        else
            cout << 'L';
    }
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen("in.txt","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
oneway.cpp:106:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         freopen("out.txt","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 50012 KB Output is correct
2 Correct 14 ms 50104 KB Output is correct
3 Correct 16 ms 50524 KB Output is correct
4 Correct 17 ms 50524 KB Output is correct
5 Correct 17 ms 50524 KB Output is correct
6 Correct 15 ms 50296 KB Output is correct
7 Correct 16 ms 50520 KB Output is correct
8 Correct 16 ms 50512 KB Output is correct
9 Correct 16 ms 50520 KB Output is correct
10 Correct 20 ms 50272 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 50012 KB Output is correct
2 Correct 14 ms 50104 KB Output is correct
3 Correct 16 ms 50524 KB Output is correct
4 Correct 17 ms 50524 KB Output is correct
5 Correct 17 ms 50524 KB Output is correct
6 Correct 15 ms 50296 KB Output is correct
7 Correct 16 ms 50520 KB Output is correct
8 Correct 16 ms 50512 KB Output is correct
9 Correct 16 ms 50520 KB Output is correct
10 Correct 20 ms 50272 KB Output is correct
11 Correct 322 ms 93012 KB Output is correct
12 Correct 371 ms 94544 KB Output is correct
13 Correct 396 ms 96560 KB Output is correct
14 Correct 428 ms 101748 KB Output is correct
15 Correct 438 ms 102664 KB Output is correct
16 Correct 497 ms 110672 KB Output is correct
17 Correct 487 ms 113156 KB Output is correct
18 Correct 547 ms 110692 KB Output is correct
19 Correct 470 ms 114572 KB Output is correct
20 Correct 347 ms 93780 KB Output is correct
21 Correct 310 ms 92240 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 50012 KB Output is correct
2 Correct 14 ms 50104 KB Output is correct
3 Correct 16 ms 50524 KB Output is correct
4 Correct 17 ms 50524 KB Output is correct
5 Correct 17 ms 50524 KB Output is correct
6 Correct 15 ms 50296 KB Output is correct
7 Correct 16 ms 50520 KB Output is correct
8 Correct 16 ms 50512 KB Output is correct
9 Correct 16 ms 50520 KB Output is correct
10 Correct 20 ms 50272 KB Output is correct
11 Correct 322 ms 93012 KB Output is correct
12 Correct 371 ms 94544 KB Output is correct
13 Correct 396 ms 96560 KB Output is correct
14 Correct 428 ms 101748 KB Output is correct
15 Correct 438 ms 102664 KB Output is correct
16 Correct 497 ms 110672 KB Output is correct
17 Correct 487 ms 113156 KB Output is correct
18 Correct 547 ms 110692 KB Output is correct
19 Correct 470 ms 114572 KB Output is correct
20 Correct 347 ms 93780 KB Output is correct
21 Correct 310 ms 92240 KB Output is correct
22 Correct 483 ms 112216 KB Output is correct
23 Correct 515 ms 109396 KB Output is correct
24 Correct 559 ms 109316 KB Output is correct
25 Correct 459 ms 116808 KB Output is correct
26 Correct 503 ms 111172 KB Output is correct
27 Correct 462 ms 109496 KB Output is correct
28 Correct 102 ms 52560 KB Output is correct
29 Correct 315 ms 93264 KB Output is correct
30 Correct 301 ms 93132 KB Output is correct
31 Correct 318 ms 94076 KB Output is correct
32 Correct 286 ms 95828 KB Output is correct