Submission #1115565

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115565		vjudge1	One-Way Streets (CEOI17_oneway)	C++17	100 / 100	117 ms	83136 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define TASK "oneway"
#define REP(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(auto i = a; i <= b; i++)
#define FORD(i, a, b) for(auto i = a; i >= b; i--)
template<class T> bool maximize(T& a, T b) { if(a < b) return a = b, 1; return 0; }
template<class T> bool minimize(T& a, T b) { if(a > b) return a = b, 1; return 0; }

using ii = pair<int, int>;
#define fi first
#define se second

const int N = (int)1e6 + 7;
int n, m, q;
vector<ii> adj[N];
vector<int> G[N], unUsed;
ii edge[N];
int isLeft[N], isRight[N], status[N]; // 1 B, 2 L, 3 R
int group[N];
ii way[N];

void Read()
{
    cin >> n >> m;
    REP(i, m)
    {
        int u, v;
        cin >> u >> v;
        edge[i] = {u, v};
        adj[u].push_back({v, i});
        adj[v].push_back({u, i});
    }
    cin >> q;
    REP(i, q)
        cin >> way[i].fi >> way[i].se;
}

int low[N], num[N], timeVis = 0, numSCC = 0;

stack<int> st;

void Tarjan(int u, int p = -1)
{
    low[u] = num[u] = ++timeVis;
    st.push(u);
    for(auto [v, id] : adj[u])
    {
        if(id == p)
            continue;
        if(low[v])
            minimize(low[u], num[v]);
        else
        {
            Tarjan(v, id);
            minimize(low[u], low[v]);
        }
    }
    if(low[u] == num[u])
    {
        int v;
        group[u] = ++numSCC;
        do
        {
            v = st.top();
            st.pop();
            group[v] = numSCC;
        } while(v != u);
    }

}

const int LOG = 31 - __builtin_clz(N);
int par[N][LOG + 3], h[N];
void LCA_Precompute(int u, int p = -1)
{
    for(auto v : G[u])
    {
        if(v == p)
            continue;
        par[v][0] = u;
        h[v] = h[u] + 1;
        REP(i, LOG)
            par[v][i] = par[par[v][i - 1]][i - 1];
        LCA_Precompute(v, u);
    }
}

int LCA(int u, int v)
{
    if(h[u] != h[v])
    {
        if(h[u] < h[v]) swap(u, v);
        int diff = h[u] - h[v];
        FOR(i, 0, LOG)
            if(diff >> i & 1) u = par[u][i];
    }
    if(u == v) return u;
    FORD(i, LOG, 0)
    {
        if(par[u][i] == par[v][i])
            continue;
        u = par[u][i];
        v = par[v][i];
    }
    return par[u][0];
}

int BinaryLifting(int u, int diff)
{
    FOR(i, 0, LOG)
    {
        if(diff >> i & 1) u = par[u][i];
    }
    return u;
}

void DFS(int u, int p = -1)
{
    for(auto v : G[u])
    {
        if(v == p)
            continue;
        DFS(v, u);
        isLeft[u] += isLeft[v];
        isRight[u] += isRight[v];
    }
}

void Solve()
{
    vector<int> root;
    REP(i, n)
    {
        if(!group[i])
        {
            Tarjan(i);
            root.push_back(group[i]);
        }
    }
    REP(i, m)
    {
        auto [u, v] = edge[i];
        u = group[u];
        v = group[v];
        if(u == v) status[i] = 1;
        else
        {
            unUsed.push_back(i);
            if(u > v) swap(u, v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
    }
    for(auto node : root)
    {
        LCA_Precompute(node);
    }
    REP(i, q)
    {
        int u = group[way[i].fi];
        int v = group[way[i].se];
        int p = LCA(u, v);
        isLeft[u]++;
        isLeft[p]--;
        isRight[p]--;
        isRight[v]++;
    }
    for(auto node : root)
        DFS(node);
    for(auto i : unUsed)
    {
        auto [u, v] = edge[i];
        u = group[u];
        v = group[v];
        if(status[i]) continue;
        if(h[u] > h[v])
        {
            swap(u, v);
            if(isLeft[v] == isRight[v]) status[i] = 1;
            else if(isLeft[v] > isRight[v]) status[i] = 3;
            else status[i] = 2;
        }
        else
        {
            if(isLeft[v] == isRight[v]) status[i] = 1;
            else if(isLeft[v] > isRight[v]) status[i] = 2;
            else status[i] = 3;
        }
    }
    REP(i, m)
    {
        if(status[i] == 2) cout << 'L';
        else if(status[i] == 3) cout << 'R';
        else
            cout << 'B';
    }
}

signed main()
{
    cin.tie(0)->ios_base::sync_with_stdio(0);

    if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
    if(fopen(TASK".INP", "r")) {
        freopen(TASK".INP", "r", stdin);
        freopen(TASK".OUT", "w", stdout);
    }

    Read();
    Solve();

    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:206:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |     if(fopen("TASK.INP", "r")) freopen("TASK.INP", "r", stdin);
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:208:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  208 |         freopen(TASK".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp:209:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  209 |         freopen(TASK".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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