Submission #1141134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141134		ALTAKEXE	Flood (IOI07_flood)	C++20	100 / 100	270 ms	29796 KiB

flood

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define inf INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) x.begin(), x.end()
const int MOD = 1e9 + 7;
using namespace std;
int x[100007], y[100007];
int p[100007][4][2];
int lev[100007 * 4], vst[100007 * 4];
vector<int> adj[4 * 100007];
int xof[4 * 100007];
int n, w;
set<pair<int, int>> s;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    cin >> w;
    for (int i = 1; i <= w; i++)
    {
        int a, b;
        cin >> a >> b;
        if (x[a] == x[b])
        {
            if (y[a] > y[b])
                swap(a, b);
            p[a][2][1] = i;
            p[a][2][0] = i + w;
            p[b][0][0] = i;
            p[b][0][1] = i + w;
            xof[i] = x[a];
            s.insert({xof[i], i});
        }
        else
        {
            if (x[a] > x[b])
                swap(a, b);
            p[a][1][0] = i;
            p[a][1][1] = i + w;
            p[b][3][1] = i;
            p[b][3][0] = i + w;
            xof[i] = 100007;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 0; j < 4; j++)
            if (p[i][j][1])
            {
                for (int k = (j + 1) % 4;; k = (k + 1) % 4)
                    if (p[i][k][0])
                    {
                        adj[p[i][j][1]].pb(p[i][k][0]);
                        adj[p[i][k][0]].pb(p[i][j][1]);
                        break;
                    }
            }
    for (int i = 1; i <= w; i++)
        lev[i] = lev[i + w] = 100007;
    while (1)
    {
        if (s.empty())
            break;
        int tmp = s.begin()->ss;
        deque<int> q;
        q.push_front(tmp);
        lev[tmp] = 0;
        while (q.size())
        {
            int x = q.front();
            q.pop_front();
            if (vst[x])
                continue;
            if (x <= w)
                s.erase({xof[x], x});
            vst[x] = 1;
            for (int y : adj[x])
            {
                if (lev[y] > lev[x])
                {
                    lev[y] = lev[x];
                    q.push_front(y);
                }
            }
            adj[x].clear();
            int k = (x > w ? x - w : x + w);
            if (lev[k] > lev[x] + 1)
            {
                lev[k] = lev[x] + 1;
                q.pb(k);
            }
        }
    }
    vector<int> ans;
    for (int i = 1; i <= w; i++)
        if (lev[i] == lev[i + w])
            ans.pb(i);
    cout << ans.size() << endl;
    for (int x : ans)
        cout << x << endl;
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 3 / 3
• Subtask 5: 10 / 10
• Subtask 6: 3 / 3
• Subtask 7: 3 / 3
• Subtask 8: 3 / 3
• Subtask 9: 3 / 3
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9
• Subtask 13: 9 / 9
• Subtask 14: 9 / 9