Submission #359276

#	Time	Username	Problem	Language	Result	Execution time	Memory
359276		blue	One-Way Streets (CEOI17_oneway)	C++17	0 / 100	1 ms	364 KiB

oneway

#include <iostream>
#include <set>
#include <vector>
#include <queue>
using namespace std;

/*
For all pairs (x, y)
If all possible routes from x to y have one or more roads in common, all such roads must be directed.

Repeatedly until there is at least one node with degree = 1:
1. Find a node with degree = 1
2. If that node has no x(+) or y(-) points, set its only edge to 'B'
3. Add all that node's + and - points to a set. Use DSU-style algoithm to combine the sets of its children.
Depending on this, set the direction for its parent edge.

After there are no more nodes with degree = 1, set all remaining edges to 'B'
*/

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

    vector<char> res(m+1, 'B');

    vector<int> edge[n+1];
    vector<int> edge_count(n+1, 0);
    int a[m+1], b[m+1];
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i] >> b[i];

        edge[a[i]].push_back(i);
        edge_count[a[i]]++;

        edge[b[i]].push_back(i);
        edge_count[b[i]]++;
    }





    int p;
    cin >> p;

    vector<int> endpoints(n+1, 0);
    int x, y;

    for(int i = 1; i <= p; i++)
    {
        cin >> x >> y;
        endpoints[x]++;
        endpoints[y]--;
    }






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

    int curr;
    int parent_edge;
    int parent;
    while(!tbv.empty())
    {
        curr = tbv.front();
        tbv.pop();

        edge_count[curr]--;

        for(int e: edge[curr])
        {
            if(edge_count[a[e] + b[e] - curr] == 0) endpoints[curr] += endpoints[a[e] + b[e] - curr];
            else parent_edge = e;
        }

        parent = a[parent_edge] + b[parent_edge] - curr;

        if(endpoints[curr] > 0)
        {
            if(a[parent_edge] == curr) res[parent_edge] = 'R';
            else res[parent_edge] = 'L';
        }
        else if(endpoints[curr] < 0)
        {
            if(a[parent_edge] == curr) res[parent_edge] = 'L';
            else res[parent_edge] = 'R';
        }

        edge_count[parent]--;
        if(edge_count[parent] == 1) tbv.push(parent);
    }

    for(int i = 1; i <= m; i++) cout << res[i];
    cout << '\n';
}

Compilation message (stderr)

oneway.cpp: In function 'int main()':
oneway.cpp:69:9: warning: 'parent_edge' may be used uninitialized in this function [-Wmaybe-uninitialized]
   69 |     int parent_edge;
      |         ^~~~~~~~~~~

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