oj.uz

Submission #1099364

# Submission time Handle Problem Language Result Execution time Memory
1099364 2024-10-11T08:45:17 Z dmn223 Circle Passing (EGOI24_circlepassing) C++14
0 / 100
 10 ms 16476 KB 
#include <bits/stdc++.h>
using namespace std;
const int dim = 1e6;
vector<vector<int>>a;
int n, m, q, x, y, r;
bool viz[dim + 1];
int dis[dim + 1], dis2[dim + 1];
void dfs(int nod, int d, int ceva[])
{
    viz[nod] = true;
    ceva[nod] = min(d, ceva[nod]);
    for(auto x : a[nod])
        if(viz[x] == false)
            dfs(x, d + 1, ceva);
}
int main()
{
    memset(dis, dim, sizeof(dis));
    memset(dis2, dim, sizeof(dis2));
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    a.resize(2 * n + 1);
    for(int i = 1; i <= m; i++)
    {
        cin >> r;
        a[r].push_back(r + n);
        a[r + n].push_back(r);
    }
    for(int i = 1; i < 2 * n; i++)
    {
        a[i].push_back(i + 1);
        a[i + 1].push_back(i);
    }
    a[0].push_back(2 * n - 1);
    a[2 * n - 1].push_back(0);

    dfs(0, 1, dis);
    memset(viz, false, sizeof(viz));
    dfs(2 * n - 1, 1, dis2);
    while(q--)
    {
        cin >> x >> y;
        int t = min(min(abs(dis[y] - dis[x] + 1), abs(dis[x] - dis[y])), min(abs(dis2[x] - dis2[y] + 1), abs(dis2[x] - dis2[y] + 1)));
        if(t == 0) cout << 1 << '\n';
        else cout << t << '\n';
    }
    return 0;
}

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9052 KB Output is correct
2 Incorrect 6 ms 9280 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 9308 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 16476 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9052 KB Output is correct
2 Incorrect 6 ms 9280 KB Output isn't correct
3 Halted 0 ms 0 KB -