Submission #104951

#	Time	Username	Problem	Language	Result	Execution time	Memory
104951		eriksuenderhauf	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	375 ms	72680 KiB

oneway

//#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 (stderr)

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 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40