oj.uz

Submission #347193

# Submission time Handle Problem Language Result Execution time Memory
347193 2021-01-12T10:01:07 Z Noran One-Way Streets (CEOI17_oneway) C++14
60 / 100
 3000 ms 20972 KB 
#include<bits/stdc++.h>

using namespace std;

#define pb push_back
#define F first
#define S second
#define debug(x) cerr<<#x<<" :"<<x<<"\n"
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define FAST ios_base::sync_with_stdio(false), cin.tie(), cout.tie();
//#define int long long

typedef long long ll;
typedef long double ld;

const int maxn = 1e5 + 7;
const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const int mlog = 19;
const int SQ = 400;

int n, m;

int a[maxn], b[maxn];

int mark[maxn], low[maxn], h[maxn];
bool dfn[maxn];

vector<pii> adj[maxn];

int par[maxn][mlog];
int f[maxn];

int parID[maxn];
int res[maxn];

int cnt = 0;

int get(int v) { return (f[v] == v ? v : get(f[v])); }

void dfs(int v)
{
    mark[v] = low[v] = ++cnt;
    for(pii Ed : adj[v])
    {
        int u = Ed.F;
        int ind = Ed.S;

        if(!mark[u])
        {
            h[u] = h[v] + 1;
            par[u][0] = v;
            parID[u] = ind;
            dfs(u);

            low[v] = min(low[u], low[v]);

            if(low[u] > mark[v]) dfn[u] = 1;
        }
        else
        {
            if(par[u][0] == v) dfn[u] = 0;
            if(u != par[v][0]) low[v] = min(low[u], low[v]);
        }
    }
}

void prep()
{
    for(int j=1;j<mlog;j++)
        for(int i=1;i<=n;i++)
            par[i][j] = par[par[i][j-1]][j-1];
}

int lca(int u,int v)
{
    if(h[u] > h[v])
        swap(u, v);

    for(int i=mlog-1;i >= 0;i--)
        if(h[par[v][i]] >= h[u])
            v = par[v][i];

    if(u == v) return v;

    for(int i=mlog-1;i>=0;i--)
    {
        if(par[u][i] != par[v][i])
        {
            u = par[u][i];
            v = par[v][i];
        }
    }

    return par[v][0];
}

int main()
{
    FAST;

    cin >> n >> m;

    for(int i=1;i<=m;i++)
    {
        cin >> a[i] >> b[i];

        adj[a[i]].pb({b[i], i});
        adj[b[i]].pb({a[i], i});
    }

    for(int i=1;i<=n;i++) if(!mark[i]) dfs(i);

    prep();

    for(int i=1;i<=n;i++) f[i] = i;

    int p;
    cin >> p;

    while(p--)
    {
        int u, v;
        cin >> u >> v;

        int lpa = lca(u, v);

        u = get(u);
        while(h[u] > h[lpa])
        {
            if(dfn[u]) res[parID[u]] = -1;
            f[u] = par[u][0];
            u = get(u);
        }

        v = get(v);
        while(h[v] > h[lpa])
        {
            if(dfn[v]) res[parID[v]] = 1;
            f[v] = par[v][0];
            v = get(v);
        }
    }

    for(int i=1;i<=n;i++)
        if(dfn[i] && b[parID[i]] != i)
            res[parID[i]] *= -1;

    for(int i=1;i<=m;i++)
    {
        if(res[i] == 1) cout << "R";
        if(res[i] == -1) cout << "L";
        if(res[i] == 0) cout << "B";
    }

    return 0;
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 2 ms 2924 KB Output is correct
4 Correct 3 ms 2924 KB Output is correct
5 Correct 3 ms 2924 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 2 ms 2796 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 2 ms 2924 KB Output is correct
4 Correct 3 ms 2924 KB Output is correct
5 Correct 3 ms 2924 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 2 ms 2796 KB Output is correct
11 Correct 56 ms 10348 KB Output is correct
12 Correct 72 ms 12524 KB Output is correct
13 Correct 89 ms 15340 KB Output is correct
14 Correct 112 ms 18540 KB Output is correct
15 Correct 115 ms 19436 KB Output is correct
16 Correct 96 ms 18412 KB Output is correct
17 Correct 99 ms 19820 KB Output is correct
18 Correct 89 ms 18412 KB Output is correct
19 Correct 107 ms 20972 KB Output is correct
20 Correct 71 ms 13684 KB Output is correct
21 Correct 59 ms 13676 KB Output is correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2668 KB Output is correct
2 Correct 3 ms 2668 KB Output is correct
3 Correct 2 ms 2924 KB Output is correct
4 Correct 3 ms 2924 KB Output is correct
5 Correct 3 ms 2924 KB Output is correct
6 Correct 3 ms 2816 KB Output is correct
7 Correct 3 ms 2924 KB Output is correct
8 Correct 3 ms 2924 KB Output is correct
9 Correct 3 ms 2796 KB Output is correct
10 Correct 2 ms 2796 KB Output is correct
11 Correct 56 ms 10348 KB Output is correct
12 Correct 72 ms 12524 KB Output is correct
13 Correct 89 ms 15340 KB Output is correct
14 Correct 112 ms 18540 KB Output is correct
15 Correct 115 ms 19436 KB Output is correct
16 Correct 96 ms 18412 KB Output is correct
17 Correct 99 ms 19820 KB Output is correct
18 Correct 89 ms 18412 KB Output is correct
19 Correct 107 ms 20972 KB Output is correct
20 Correct 71 ms 13684 KB Output is correct
21 Correct 59 ms 13676 KB Output is correct
22 Execution timed out 3074 ms 20336 KB Time limit exceeded
23 Halted 0 ms 0 KB -