Submission #878682

#	Time	Username	Problem	Language	Result	Execution time	Memory
878682		Ghulam_Junaid	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	3 ms	14936 KiB

oneway

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int n, m, p, deg[N];
int out[N], in[N];

vector<int> g[N], paired[N];
set<int> waiting_in[N], waiting_out[N];
map<pair<int, int>, int> edge;
vector<pair<int, int>> edges;

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

    string s;
    for (int i=0; i<m; i++){
        int u, v;
        cin >> u >> v;

        if (u != v){
            g[u].push_back(v);
            g[v].push_back(u);
            deg[u]++;
            deg[v]++;
            edge[{u, v}] = edge[{v, u}] = i;
        }
        edges.push_back({u, v});

        s += 'B';
    }

    cin >> p;
    for (int i=0; i<p; i++){
        int u, v;
        cin >> u >> v;

        out[u]++;
        in[v]++;

        // paired[v].push_back(u);
        // paired[u].push_back(v);

        waiting_in[v].insert(u);
        waiting_out[u].insert(v);
    }

    queue<int> q;
    for (int i=1; i<=n; i++)
        if (deg[i] == 1)
            q.push(i);

    while (!q.empty()){
        int v = q.front();
        deg[v]--;
        // if (g[v].size() > 1){
        //     cout << endl << "ERROR, degree is not 1" << endl << endl;
        // }

        int u = g[v][0];
        q.pop();

        int id = edge[{v, u}];

        // cout << v << " prev char = " << s[id] << " new char = ";

        // cout << "id = " << id << endl;

        if (waiting_in[v].size()){
            // cout << "here 1" << endl;
            if (edges[id].first == u)
                s[id] = 'R';
            else
                s[id] = 'L';

            deg[u]--;
            if (deg[u] == 1)
                q.push(u);

            for (int x : waiting_in[v]){
                waiting_out[x].erase(v);
                if (x == u) continue;
                waiting_in[u].insert(x);
                waiting_out[x].insert(u);
            }
            waiting_in[v].clear();
        }
        else if (waiting_out[v].size()){
            // cout << "here 2" << endl;
            if (edges[id].first == v)
                s[id] = 'R';
            else
                s[id] = 'L';

            deg[u]--;
            if (deg[u] == 1)
                q.push(u);

            for (int x : waiting_out[v]){
                waiting_in[x].erase(v);
                if (u == x) continue;
                waiting_out[u].insert(x);
                waiting_in[x].insert(u);
            }
            waiting_out[v].clear();
        }
        else{
            deg[u]--;
            if (deg[u] == 1)
                q.push(u);
        }

        // cout << s[id] << endl;
    }

    cout << s << endl;
}

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