Submission #131550

#	Time	Username	Problem	Language	Result	Execution time	Memory
131550		SamAnd	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	456 ms	46840 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
const int N = 100005, l = 20;

int n, m;
pair<int, int> r[N];
vector<int> a[N];
vector<int> b[N];

bool bri[N];

int c[N];
int tin[N], ti, fup[N];
void dfs0(int x, int p)
{
    c[x] = 1;
    fup[x] = tin[x] = ti++;
    for (int i = 0; i < a[x].size(); ++i)
    {
        int h = a[x][i];
        if (h == p)
            continue;
        if (c[h])
            fup[x] = min(fup[x], tin[h]);
        else
        {
            dfs0(h, x);
            if (fup[h] > tin[x])
                bri[b[x][i]] = true;
            fup[x] = min(fup[x], fup[h]);
        }
    }
}

int k;
void dfs1(int x)
{
    c[x] = k;
    for (int i = 0; i < a[x].size(); ++i)
    {
        if (bri[b[x][i]])
            continue;
        int h = a[x][i];
        if (!c[h])
            dfs1(h);
    }
}

vector<int> g[N];
vector<int> gg[N];
bool c1[N];
int tout[N];
int pp[N][l];
bool dfs(int x, int p)
{
    c1[x] = true;
    tin[x] = ti++;
    pp[x][0] = p;
    for (int i = 1; i < l; ++i)
    {
        pp[x][i] = pp[pp[x][i - 1]][i - 1];
    }
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfs(h, x);
    }
    tout[x] = ti++;
}
bool par(int x, int y)
{
    return (tin[x] <= tin[y] && tout[x] >= tout[y]);
}
int lca(int x, int y)
{
    if (par(x, y))
        return x;
    if (par(y, x))
        return y;
    for (int i = l - 1; i >= 0; --i)
    {
        if (!par(pp[x][i], y))
            x = pp[x][i];
    }
    return pp[x][0];
}

char ans[N];

int qu[N], qd[N];
void dfsf(int x, int p, int j)
{
    for (int i = 0; i < g[x].size(); ++i)
    {
        int h = g[x][i];
        if (h == p)
            continue;
        dfsf(h, x, gg[x][i]);
        qu[x] += qu[h];
        qd[x] += qd[h];
    }
    if (qu[x])
    {
        if (m_p(x, p) == m_p(c[r[j].first], c[r[j].second]))
            ans[j - 1] = 'R';
        else
            ans[j - 1] = 'L';
    }
    if (qd[x])
    {
        if (m_p(p, x) == m_p(c[r[j].first], c[r[j].second]))
            ans[j - 1] = 'R';
        else
            ans[j - 1] = 'L';
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    map<pair<int, int> , int> mp;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
        b[x].push_back(i);
        b[y].push_back(i);
        r[i] = m_p(x, y);
        if (x > y)
            swap(x, y);
        mp[m_p(x, y)]++;
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!c[i])
            dfs0(i, -1);
    }
    for (int i = 1; i <= m; ++i)
    {
        if (bri[i])
        {
            if (mp[m_p(min(r[i].first, r[i].second), max(r[i].first, r[i].second))] > 1)
                bri[i] = false;
        }
    }
    memset(c, 0, sizeof c);
    for (int x = 1; x <= n; ++x)
    {
        if (!c[x])
        {
            ++k;
            dfs1(x);
        }
    }
    for (int x = 1; x <= n; ++x)
    {
        for (int i = 0; i < a[x].size(); ++i)
        {
            if (bri[b[x][i]])
            {
                g[c[x]].push_back(c[a[x][i]]);
                gg[c[x]].push_back(b[x][i]);
            }
        }
    }

    for (int i = 1; i <= m; ++i)
        ans[i - 1] = 'B';

    vector<int> v;
    for (int i = 1; i <= k; ++i)
    {
        if (!c1[i])
        {
            v.push_back(i);
            dfs(i, i);
        }
    }

    int q;
    scanf("%d", &q);
    while (q--)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        x = c[x];
        y = c[y];
        int t = lca(x, y);
        qu[x]++;
        qu[t]--;
        qd[y]++;
        qd[t]--;
    }
    for (int i = 0; i < v.size(); ++i)
    {
        dfsf(v[i], v[i], -1);
    }
    cout << ans << endl;
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void dfs0(int, int)':
oneway.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'void dfs1(int)':
oneway.cpp:40:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < a[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'bool dfs(int, int)':
oneway.cpp:64:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
oneway.cpp:72:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
oneway.cpp: In function 'void dfsf(int, int, int)':
oneway.cpp:96:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < g[x].size(); ++i)
                     ~~^~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:164:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < a[x].size(); ++i)
                         ~~^~~~~~~~~~~~~
oneway.cpp:201:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < v.size(); ++i)
                     ~~^~~~~~~~~~
oneway.cpp:125:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:129:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~
oneway.cpp:188:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
oneway.cpp:192:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &x, &y);
         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 30 / 30
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40