Submission #1091155

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091155		raphaelp	One-Way Streets (CEOI17_oneway)	C++14	0 / 100	0 ms	348 KiB

oneway

#include <bits/stdc++.h>
using namespace std;
int dfs(int x, int p, int id, vector<vector<pair<int, int>>> &AR, int &buff, vector<int> &ordre, vector<int> &low, vector<int> &incycle)
{
    if (low[x] != low.size())
    {
        incycle.push_back(id);
        return low[x];
    }
    ordre[x] = buff;
    low[x] = buff++;
    int left = 1;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i].first == p && left)
        {
            left--;
            continue;
        }
        low[x] = min(low[x], dfs(AR[x][i].first, x, AR[x][i].second, AR, buff, ordre, low, incycle));
    }
    if (low[x] < ordre[x])
        incycle.push_back(id);
    return low[x];
}
int find(int x, vector<int> &p)
{
    return (p[x] == x) ? x : p[x] = find(p[x], p);
}
int dfs2(int x, int par, int id, vector<int> &p, vector<vector<pair<int, int>>> &AR, vector<int> &cities, vector<char> &ans, vector<pair<int, int>> &aretes)
{
    int cur = 0;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (find(AR[x][i].first, p) == par)
            continue;
        if (find(AR[x][i].first, p) == x)
            continue;
        cur += dfs2(find(AR[x][i].first, p), x, AR[x][i].second, p, AR, cities, ans, aretes);
    }
    cur += cities[x];
    if (id < 0)
        return cur;
    if (cur == 0)
        ans[id] = 'B';
    else
    {
        if (find(aretes[id].first, p) == x)
        {
            if (cur > 0)
                ans[id] = 'R';
            else
                ans[id] = 'L';
        }
        else
        {
            if (cur > 0)
                ans[id] = 'L';
            else
                ans[id] = 'R';
        }
    }
    return cur;
}
int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<pair<int, int>>> AR(N);
    vector<pair<int, int>> aretes;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        AR[a].push_back({b, i});
        AR[b].push_back({a, i});
        aretes.push_back({a, b});
    }
    int buff = 0;
    vector<int> low(N, N), ordre(N);
    vector<int> incycle;
    dfs(0, 0, -1, AR, buff, ordre, low, incycle);
    vector<char> ans(M);
    vector<int> p(N), size(N, 1);
    for (int i = 0; i < N; i++)
        p[i] = i;
    for (int i = 0; i < incycle.size(); i++)
    {
        ans[incycle[i]] = 'B';
        int x = find(aretes[incycle[i]].first, p), y = find(aretes[incycle[i]].second, p);
        if (x == y)
            continue;
        if (size[x] > size[y])
            swap(x, y);
        p[x] = y;
        size[y] += size[x];
        for (int j = 0; j < AR[x].size(); j++)
            AR[y].push_back(AR[x][j]);
    }
    int P;
    cin >> P;
    vector<int> cities(N, 0);
    for (int i = 0; i < P; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        cities[find(a, p)]++;
        cities[find(b, p)]--;
    }
    int temp = dfs2(find(0, p), find(0, p), -1, p, AR, cities, ans, aretes);
    for (int i = 0; i < M; i++)
        cout << ans[i];
}

Compilation message (stderr)

oneway.cpp: In function 'int dfs(int, int, int, std::vector<std::vector<std::pair<int, int> > >&, int&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
oneway.cpp:5:16: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 |     if (low[x] != low.size())
oneway.cpp:13:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp: In function 'int dfs2(int, int, int, std::vector<int>&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<int>&, std::vector<char>&, std::vector<std::pair<int, int> >&)':
oneway.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < incycle.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
oneway.cpp:98:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for (int j = 0; j < AR[x].size(); j++)
      |                         ~~^~~~~~~~~~~~~~
oneway.cpp:112:9: warning: unused variable 'temp' [-Wunused-variable]
  112 |     int temp = dfs2(find(0, p), find(0, p), -1, p, AR, cities, ans, aretes);
      |         ^~~~

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