Submission #320680

#	Time	Username	Problem	Language	Result	Execution time	Memory
320680		phathnv	One-Way Streets (CEOI17_oneway)	C++11	100 / 100	126 ms	23780 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define X first
#define Y second
#define mp make_pair

typedef long long ll;
typedef pair <int, int> ii;

const int N = 1e5 + 1;
const int logN = 17;

struct edge{
    int u, v;
    edge(int _u = 0, int _v = 0){
        u = _u;
        v = _v;
    }
};

struct dsu{
    int root[N], rnk[N];
    void reset(int n){
        for(int i = 1; i <= n; i++){
            root[i] = i;
            rnk[i] = 0;
        }
    }
    int getRoot(int u){
        if (u == root[u])
            return u;
        root[u] = getRoot(root[u]);
        return root[u];
    }
    bool unite(int u, int v){
        u = getRoot(u);
        v = getRoot(v);
        if (u == v)
            return 0;
        if (rnk[u] < rnk[v])
            swap(u, v);
        root[v] = u;
        rnk[u] += (rnk[u] == rnk[v]);
        return 1;
    }
} G;

int n, m, p;
edge e[N];

bool used[N];
vector <ii> adj[N];
int h[N], par[N][logN], edgeToPar[N], cnt[N], dir[N];
char ans[N];


int inComp[N], nComp;

void readInput(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
        scanf("%d %d", &e[i].u, &e[i].v);
}

void dfs(int u, int p){

    inComp[u] = nComp;

    for(int i = 1; i < logN; i++)
        par[u][i] = par[par[u][i - 1]][i - 1];
    for(ii e : adj[u]){
        int v = e.X;
        int id = e.Y;
        if (v != p){
            h[v] = h[u] + 1;
            par[v][0] = u;
            edgeToPar[v] = id;
            dfs(v, u);
        }
    }
}

int getLCA(int u, int v){
    if (h[u] > h[v])
        swap(u, v);
    for(int i = logN - 1; i >= 0; i--)
        if (h[u] <= h[v] - (1 << i))
            v = par[v][i];
    if (u == v)
        return u;
    for(int i = logN - 1; i >= 0; i--)
        if (par[u][i] != par[v][i]){
            u = par[u][i];
            v = par[v][i];
        }
    return par[u][0];
}

void slowMarkNotCutEdge(int u, int v){
    while (u != v){
        if (h[u] > h[v])
            swap(u, v);
        cnt[v]++;
        v = par[v][0];
    }
}

void slowMarkDir(int u, int v){
    while (u != v){
        if (h[u] > h[v]){
            dir[u]--;
            u = par[u][0];
        } else {
            dir[v]++;
            v = par[v][0];
        }
    }
}

void markNotCutEdge(int u, int v){
    int lca = getLCA(u, v);
    cnt[u]++;
    cnt[v]++;
    cnt[lca] -= 2;
}

void markDir(int u, int v){
    dir[u]--;
    dir[v]++;
}

void dfs2(int u, int p){
    for(ii e : adj[u]){
        int v = e.X;
        if (v != p){
            dfs2(v, u);
            cnt[u] += cnt[v];
            dir[u] += dir[v];
        }
    }
}

void prepare(){
    G.reset(n);
    for(int i = 1; i <= m; i++)
        if (G.unite(e[i].u, e[i].v)){
            used[i] = 1;
            adj[e[i].u].push_back(mp(e[i].v, i));
            adj[e[i].v].push_back(mp(e[i].u, i));
        }
    for(int i = 1; i <= n; i++)
        if (!par[i][0]){
            ++nComp;
            dfs(i, -1);
        }
    for(int i = 1; i <= m; i++)
        if (!used[i])
            markNotCutEdge(e[i].u, e[i].v);
}

void solve(){
    scanf("%d", &p);
    for(int i = 1; i <= p; i++){
        int u, v;
        scanf("%d %d", &u, &v);
        markDir(u, v);
    }
    memset(ans, 'B', sizeof(ans));

    for(int i = 1; i <= n; i++)
        if (par[i][0] == 0)
            dfs2(i, -1);

    for(int i = 1; i <= n; i++)
        if (par[i][0]){
            if (cnt[i] > 0 || dir[i] == 0)
                continue;
            int id = edgeToPar[i];
            if (dir[i] < 0)
                ans[id] = (e[id].u == i? 'R' : 'L');
            else
                ans[id] = (e[id].u == i? 'L' : 'R');
        }

    for(int i = 1; i <= m; i++)
        putchar(ans[i]);
}

int main(){
    readInput();
    prepare();
    solve();
    return 0;
}

Compilation message (stderr)

oneway.cpp: In function 'void readInput()':
oneway.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   62 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
oneway.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   64 |         scanf("%d %d", &e[i].u, &e[i].v);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
oneway.cpp: In function 'void solve()':
oneway.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  164 |     scanf("%d", &p);
      |     ~~~~~^~~~~~~~~~
oneway.cpp:167:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  167 |         scanf("%d %d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~~

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