oj.uz

Submission #104951

# Submission time Handle Problem Language Result Execution time Memory
104951 2019-04-10T00:18:41 Z eriksuenderhauf One-Way Streets (CEOI17_oneway) C++11
100 / 100
 375 ms 72680 KB 
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define enl printf("\n")
#define case(t) printf("Case #%d: ", (t))
#define ni(n) scanf("%d", &(n))
#define nl(n) scanf("%I64d", &(n))
#define nai(a, n) for (int i = 0; i < (n); i++) ni(a[i])
#define nal(a, n) for (int i = 0; i < (n); i++) nl(a[i])
#define pri(n) printf("%d\n", (n))
#define prl(n) printf("%I64d\n", (n))
#define pii pair<int, int>
#define pll pair<long long, long long>
#define vii vector<pii>
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef long long ll;
const double pi = acos(-1);
const int MOD = 1e9 + 7;
const int INF = 1e9 + 7;
const int MAXN = 1e5 + 5;
const double eps = 1e-9;
int U[MAXN], V[MAXN], ans[MAXN], br[MAXN], id[MAXN];
bool vis[MAXN], mrk[MAXN];
int low[MAXN], disc[MAXN];
int npar[20][MAXN], depth[MAXN], f[MAXN];
int qry[MAXN][3];
vii adj[MAXN], tree[MAXN];
int t = 0;

void dfs(int u, int p)
{
    low[u] = disc[u] = t++;
    vis[u] = 1;
    for (pii nx: adj[u])
    {
        int v = nx.fi;
        if (nx.se == p)
            continue;
        if (!vis[v])
        {
            dfs(v, nx.se);
            low[u] = min(low[u], low[v]);
            if (low[v] > disc[u])
                br[nx.se] = 1;
        }
        else
            low[u] = min(low[u], disc[v]);
    }
}

int cur = 0;

void tr(int u)
{
    deque<int> pq;
    pq.pb(u);
    vis[u] = 1;
    int cmp = cur;
    id[u] = cmp;
    while (!pq.empty())
    {
        int ur = pq.front(); pq.pop_front();
        for (pii nx: adj[ur])
        {
            int v = nx.fi;
            if (vis[v])
                continue;
            if (br[nx.se])
            {
                cur++;
                tree[cur].pb({cmp, nx.se});
                tree[cmp].pb({cur, nx.se});
                tr(v);
            }
            else
            {
                pq.pb(v);
                id[v] = cmp;
                vis[v] = 1;
            }
        }
    }
}

void dfs2(int u, int p, int d)
{
    depth[u] = d;
    for (pii nx: tree[u])
    {
        int v = nx.fi;
        if (v != p)
        {
            f[v] = nx.se;
            dfs2(v, u, d + 1);
            npar[0][v] = u;
        }
    }
}

int lca(int u, int v)
{
    if (depth[u] > depth[v])
        swap(u, v);
    int d = depth[v] - depth[u];
    for (int i = 16; i >= 0; i--)
        if ((d >> i) & 1)
            v = npar[i][v];
    if (u == v)
        return v;
    for (int i = 16; i >= 0; i--)
        if (npar[i][u] != npar[i][v])
            u = npar[i][u], v = npar[i][v];
    return npar[0][u];
}

int main()
{
    int n, m, p;
    ni(n), ni(m);
    for (int i = 0; i < m; i++)
    {
        ni(U[i]), ni(V[i]);
        U[i]--, V[i]--;
        adj[U[i]].pb({V[i], i});
        adj[V[i]].pb({U[i], i});
    }
    int c = 0;
    vi tmp, tmp2;
    for (int i = 0; i < n; i++)
        if (!vis[i])
            dfs(i, -1), c++, tmp.pb(i);
    memset(vis, 0, sizeof vis);
    for (int i = 0; i < c; i++)
        tmp2.pb(cur), tr(tmp[i]), cur++;
    for (int i= 0; i < c; i++)
        dfs2(tmp2[i], -1, 0);
    for (int i = 1; i < 17; i++)
        for (int j = 0; j < cur; j++)
            npar[i][j] = npar[i - 1][npar[i - 1][j]];
    vii arr;
    ni(p);
    for (int i = 0; i < p; i++)
    {
        int u, v;
        ni(u), ni(v);
        u--, v--;
        u = id[u], v = id[v];
        if (u == v)
            continue;
        int l = lca(u, v);
        arr.pb({depth[l], i});
        qry[i][0] = u, qry[i][1] = v, qry[i][2] = l;
    }
    sort(arr.begin(), arr.end());
    for (pii nx: arr)
    {
        int u = qry[nx.se][0], v = qry[nx.se][1], l = qry[nx.se][2];
        int x = u;
        while (x != l)
        {
            if (mrk[f[x]])
                break;
            mrk[f[x]] = 1;
            if (id[U[f[x]]] == x)
                ans[f[x]] = 2;
            else
                ans[f[x]] = 1;
            x = npar[0][x];
        }
        x = v;
        while (x != l)
        {
            if (mrk[f[x]])
                break;
            mrk[f[x]] = 1;
            if (id[U[f[x]]] == x)
                ans[f[x]] = 1;
            else
                ans[f[x]] = 2;
            x = npar[0][x];
        }
    }
    for (int i = 0; i < m; i++)
        if (ans[i] == 0)
            printf("B");
        else if (ans[i] == 1)
            printf("L");
        else
            printf("R");
    enl;
    return 0;
}

Compilation message

oneway.cpp: In function 'int main()':
oneway.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     ni(n), ni(m);
          ^
oneway.cpp:123:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
oneway.cpp:126:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         ni(U[i]), ni(V[i]);
                 ^
oneway.cpp:126:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
oneway.cpp:5:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 #define ni(n) scanf("%d", &(n))
               ~~~~~^~~~~~~~~~~~
oneway.cpp:145:5: note: in expansion of macro 'ni'
     ni(p);
     ^~
oneway.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         ni(u), ni(v);
              ^
oneway.cpp:149:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 8 ms 5376 KB Output is correct
4 Correct 9 ms 5376 KB Output is correct
5 Correct 8 ms 5760 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5760 KB Output is correct
8 Correct 8 ms 5504 KB Output is correct
9 Correct 8 ms 5376 KB Output is correct
10 Correct 8 ms 5504 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 8 ms 5376 KB Output is correct
4 Correct 9 ms 5376 KB Output is correct
5 Correct 8 ms 5760 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5760 KB Output is correct
8 Correct 8 ms 5504 KB Output is correct
9 Correct 8 ms 5376 KB Output is correct
10 Correct 8 ms 5504 KB Output is correct
11 Correct 78 ms 11100 KB Output is correct
12 Correct 89 ms 12568 KB Output is correct
13 Correct 96 ms 13816 KB Output is correct
14 Correct 126 ms 16868 KB Output is correct
15 Correct 133 ms 18292 KB Output is correct
16 Correct 150 ms 23796 KB Output is correct
17 Correct 210 ms 38640 KB Output is correct
18 Correct 195 ms 24348 KB Output is correct
19 Correct 201 ms 50960 KB Output is correct
20 Correct 71 ms 11768 KB Output is correct
21 Correct 73 ms 12884 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5248 KB Output is correct
2 Correct 7 ms 5248 KB Output is correct
3 Correct 8 ms 5376 KB Output is correct
4 Correct 9 ms 5376 KB Output is correct
5 Correct 8 ms 5760 KB Output is correct
6 Correct 8 ms 5376 KB Output is correct
7 Correct 8 ms 5760 KB Output is correct
8 Correct 8 ms 5504 KB Output is correct
9 Correct 8 ms 5376 KB Output is correct
10 Correct 8 ms 5504 KB Output is correct
11 Correct 78 ms 11100 KB Output is correct
12 Correct 89 ms 12568 KB Output is correct
13 Correct 96 ms 13816 KB Output is correct
14 Correct 126 ms 16868 KB Output is correct
15 Correct 133 ms 18292 KB Output is correct
16 Correct 150 ms 23796 KB Output is correct
17 Correct 210 ms 38640 KB Output is correct
18 Correct 195 ms 24348 KB Output is correct
19 Correct 201 ms 50960 KB Output is correct
20 Correct 71 ms 11768 KB Output is correct
21 Correct 73 ms 12884 KB Output is correct
22 Correct 356 ms 41660 KB Output is correct
23 Correct 273 ms 27492 KB Output is correct
24 Correct 298 ms 27512 KB Output is correct
25 Correct 375 ms 72680 KB Output is correct
26 Correct 300 ms 38376 KB Output is correct
27 Correct 246 ms 27576 KB Output is correct
28 Correct 54 ms 9208 KB Output is correct
29 Correct 121 ms 14548 KB Output is correct
30 Correct 121 ms 15384 KB Output is correct
31 Correct 134 ms 14452 KB Output is correct
32 Correct 210 ms 37588 KB Output is correct