Submission #1099364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099364		dmn223	Circle Passing (EGOI24_circlepassing)	C++14	0 / 100	10 ms	16476 KiB

Main

#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 / 14
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 17
• Subtask 5: 0 / 27