Submission #486734

#	Time	Username	Problem	Language	Result	Execution time	Memory
486734		pppickleman	One-Way Streets (CEOI17_oneway)	C++11	0 / 100	1 ms	1100 KiB

oneway

#include <bits/stdc++.h>

using namespace std;

#define pii pair<int, int>
#define f first
#define s second

int n, m, a, b, l, p;
int pre[100000];
int ind[100000];
pii edge[100000];
int back[100000];
int val[100000];
int val2[100000];
int starts[100];
int finishes[100];
int visited[100000];
char dir[100000];
vector<int> cycle;
vector<int> adj[1000];
string ans;

int next(pii x, int u)
{
    return x.f ^ x.s ^ u;
}

void dfs(int n)
{    
    for (auto e : adj[n]){
        int v = next(edge[e], n);

        if (v != pre[n]){
            if (ind[v] == 1e9){
                ind[v] = min(ind[v], ind[n] + 1);
                pre[v] = n;
                dfs(v);
                val[n] += val[v];
                if (val[v] != 0)
                    cycle.push_back(e);
            } else {
                if (ind[v] <= ind[n]){
                    val[n]++;
                    val[v]--;
                    cycle.push_back(e);
                    dir[e] = 'B';
                }
            }
        }
    }
}

void dfs2(int n)
{
    for (auto e : adj[n]){
        int v = next(edge[e], n);

        if (ind[n] <= ind[v] && dir[e] != 'B'){
            dfs2(v);
            val2[n] += val2[v];
        }
    }
}

int main ()
{
    cin >> n >> m;

    int rept;

    for (int i = 0; i < m; i++){
        cin >> a >> b;
        rept = 0;
        for (int j = 0; j < adj[a - 1].size(); j++){
            if (b - 1 == next(edge[adj[a - 1][j]], a - 1))
                rept = 1;
        }
        if (rept == 0){
            edge[i].f = a - 1;
            edge[i].s = b - 1;
            adj[a - 1].push_back(i);
            adj[b - 1].push_back(i);
        }
    }

    for (int i = 0; i < n; i++){
        ind[i] = 1e9;
    }

    ind[0] = 1;

    memset(val, 0, sizeof(val));

    dfs(0);

    cin >> p;

    for (int i = 0; i < p; i++){
        cin >> a >> b;
        starts[i] = a - 1;
        finishes[i] = b - 1;
    }

    memset(val2, 0, sizeof(val));

    for (int i = 0; i < p; i++){
        val2[starts[i]]++;
        val2[finishes[i]]--;
    }

    dfs2(0);

    int k;

    for (int i = 0; i < m; i++){
        if (ind[edge[i].f] > ind[edge[i].s])
            k = val2[edge[i].f];
        else
            k = val2[edge[i].s];
        
        if (k > 0)
            dir[i] = 'R';
        else if (k < 0)
            dir[i] = 'L';
        else
            dir[i] = 'B';
    }

    for (int i = 0; i < m; i++)
        cout << dir[i];
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:75:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j = 0; j < adj[a - 1].size(); j++){
      |                         ~~^~~~~~~~~~~~~~~~~~~

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