Submission #814412

#	Time	Username	Problem	Language	Result	Execution time	Memory
814412		PixelCat	Fountain Parks (IOI21_parks)	C++17	70 / 100	835 ms	99172 KiB

parks

#include "parks.h"

#ifdef NYAOWO
#include "grader.cpp"
#endif

#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define eb emplace_back
// #define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;

const int MAXN = 200'000;
const int MAXND = MAXN * 2;

struct SCC {
    vector<int> adj[MAXND + 10];
    vector<int> rev[MAXND + 10];
    int vis[MAXND + 10];
    vector<int> stk;
 
    void link(int x, int y) {
        adj[x].eb(y);
        rev[y].eb(x);
    }
    void bilink(int x, int y) {
        link(x, y);
        link(y, x);
    }
 
    void dfs1(int n) {
        if(vis[n] < 0) return;
        vis[n] = -1;
        for(auto &i:rev[n]) dfs1(i);
        stk.eb(n);
    }
    void dfs2(int n, int tag) {
        if(vis[n] != -1) return;
        vis[n] = tag;
        for(auto &i:adj[n]) dfs2(i, tag);
    }
    int build_scc(int n) {
        memset(vis, 0, sizeof(vis));
        For(i, 0, n - 1) dfs1(i);
        int cur_scc = 0;
        while(sz(stk)) {
            dfs2(stk.back(), cur_scc);
            while(sz(stk) && vis[stk.back()] != -1) stk.pop_back();
            cur_scc++;
        }
        return cur_scc;
    }
} ayaya;

struct DSU {
    int p[MAXN + 10];
    void init() {
        memset(p, -1, sizeof(p));
    }
    int find(int n) {
        if(p[n] < 0) return n;
        return p[n] = find(p[n]);
    }
    bool uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return false;
        p[b] = a;
        return true;
    }
} dsu;

vector<pii> pos[MAXN + 10];

int construct_roads(std::vector<int> X, std::vector<int> Y) {
    if (sz(X) == 1) {
        build({}, {}, {}, {});
        return 1;
    }
    int n = sz(X);

    map<pii, int> mp;
    For(i, 0, n - 1) {
        mp[pii(X[i], Y[i])] = i;
        pos[X[i]].eb(Y[i], i);
    }
    auto find = [&](int x, int y) {
        if(mp.count(pii(x, y))) return mp[pii(x, y)];
        return -1;
    };
    dsu.init();
    int cnt = 0;
    map<pii, int> hor, ver;
    vector<int> U(n - 1), V(n - 1), A(n - 1), B(n - 1);
    for(int x = 2; x <= MAXN; x += 2) {
        for(auto &it:pos[x]) {
            int y, i;
            tie(y, i) = it;
            auto link = [&](int x2, int y2) {
                int j = find(x2, y2);
                if(j >= 0 && dsu.uni(i, j)) {
                    if(x2 == x) ver[pii(x, max(y, y2))] = cnt;
                    else hor[pii(min(x, x2), y)] = cnt;
                    U[cnt] = i;
                    V[cnt] = j;
                    cnt++;
                }
            };
            link(x + 2, y);
            link(x, y + 2);
        }
    }
    // For(i, 0, n - 1) {
    //     int x = X[i], y = Y[i];
    //     auto link = [&](int x2, int y2) {
    //         int j = find(x2, y2);
    //         if(j >= 0 && dsu.uni(i, j)) {
    //             if(x2 == x) ver[pii(x, max(y, y2))] = cnt;
    //             else hor[pii(min(x, x2), y)] = cnt;
    //             U[cnt] = i;
    //             V[cnt] = j;
    //             cnt++;
    //         }
    //     };
    //     const int dx[4] = {0, 0, 2, -2};
    //     const int dy[4] = {2, -2, 0, 0};
    //     For(it, 0, 3) link(x + dx[it], y + dy[it]);
    // }
    if(cnt != n - 1) return 0;

    for(auto &it:ver) {
        pii p; int id;
        tie(p, id) = it;
        int x, y;
        tie(x, y) = p;
        if(hor.count(pii(x - 2, y))) {
            int id2 = hor[pii(x - 2, y)];
            ayaya.link(id, id2);
            ayaya.link(id2 + n, id + n);
        }
        if(hor.count(pii(x - 2, y - 2))) {
            int id2 = hor[pii(x - 2, y - 2)];
            ayaya.link(id, id2 + n);
            ayaya.link(id2, id + n);
        }
        if(hor.count(pii(x, y))) {
            int id2 = hor[pii(x, y)];
            ayaya.link(id + n, id2);
            ayaya.link(id2 + n, id);
        }
        if(hor.count(pii(x, y - 2))) {
            int id2 = hor[pii(x, y - 2)];
            ayaya.link(id + n, id2 + n);
            ayaya.link(id2, id);
        }
        if(ver.count(pii(x + 2, y))) {
            int id2 = ver[pii(x + 2, y)];
            ayaya.link(id + n, id2 + n);
            ayaya.link(id2, id);
        }
    }
    for(auto &it:hor) {
        pii p; int id;
        tie(p, id) = it;
        int x, y;
        tie(x, y) = p;
        if(hor.count(pii(x, y - 2))) {
            int id2 = hor[pii(x, y - 2)];
            ayaya.link(id + n, id2 + n);
            ayaya.link(id2, id);
        }
    }
    ayaya.build_scc(n * 2);

    for(auto &it:ver) {
        pii p; int id;
        tie(p, id) = it;
        int x, y;
        tie(x, y) = p;
        int s1 = ayaya.vis[id];
        int s2 = ayaya.vis[id + n];
        if(s1 == s2) return 0;
        if(s1 < s2) {
            A[id] = x - 1;
            B[id] = y - 1;
        } else {
            A[id] = x + 1;
            B[id] = y - 1;
        }
    }
    for(auto &it:hor) {
        pii p; int id;
        tie(p, id) = it;
        int x, y;
        tie(x, y) = p;
        int s1 = ayaya.vis[id];
        int s2 = ayaya.vis[id + n];
        if(s1 == s2) return 0;
        if(s1 < s2) {
            A[id] = x + 1;
            B[id] = y + 1;
        } else {
            A[id] = x + 1;
            B[id] = y - 1;
        }
    }
    build(U, V, A, B);
    return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30