oj.uz

Submission #1091446

# Submission time Handle Problem Language Result Execution time Memory
1091446 2024-09-20T21:50:17 Z raphaelp One-Way Streets (CEOI17_oneway) C++14
30 / 100
 51 ms 11212 KB 
#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, vector<int> &occ)
{
    occ[x] = 1;
    if (low[x] != low.size())
    {
        incycle.push_back(id);
        return low[x];
    }
    ordre[x] = buff;
    low[x] = buff++;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i].second == id)
            continue;
        low[x] = min(low[x], dfs(AR[x][i].first, x, AR[x][i].second, AR, buff, ordre, low, incycle, occ));
    }
    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, vector<int> &occ)
{
    occ[x] = 1;
    int cur = 0;
    for (int i = 0; i < AR[x].size(); i++)
    {
        if (AR[x][i].second == id)
            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, occ);
    }
    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;
    vector<int> occ(N);
    for (int i = 0; i < N; i++)
    {
        if (occ[i])
            continue;
        int temp = dfs(i, i, -1, AR, buff, ordre, low, incycle, occ);
    }
    vector<char> ans(M);
    vector<int> p(N), size(N, 1);
    for (int i = 0; i < N; i++)
        size[i] = AR[i].size();
    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 (auto j : AR[x])
            AR[y].push_back(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)]--;
    }
    occ.assign(N, 0);
    for (int i = 0; i < N; i++)
    {
        if (occ[i])
            continue;
        if (N <= 1000 && M <= 1000)
            int temp = dfs2(find(i, p), find(i, p), -1, p, AR, cities, ans, aretes, occ);
    }
    for (int i = 0; i < M; i++)
        cout << ans[i];
}

Compilation message

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>&, std::vector<int>&)':
oneway.cpp:6: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]
    6 |     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> >&, std::vector<int>&)':
oneway.cpp:31: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]
   31 |     for (int i = 0; i < AR[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~
oneway.cpp: In function 'int main()':
oneway.cpp:86:13: warning: unused variable 'temp' [-Wunused-variable]
   86 |         int temp = dfs(i, i, -1, AR, buff, ordre, low, incycle, occ);
      |             ^~~~
oneway.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for (int i = 0; i < incycle.size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~
oneway.cpp:124:17: warning: unused variable 'temp' [-Wunused-variable]
  124 |             int temp = dfs2(find(i, p), find(i, p), -1, p, AR, cities, ans, aretes, occ);
      |                 ^~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 584 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 600 KB Output is correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 584 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Incorrect 51 ms 11212 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 584 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 348 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Incorrect 51 ms 11212 KB Output isn't correct
12 Halted 0 ms 0 KB -