Submission #1215573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215573		dosts	Fountain Parks (IOI21_parks)	C++20	55 / 100	901 ms	106100 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
//#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9;


struct DSU {
    vi dad;
    DSU(){}
    DSU(int nn) {
        dad.resize(nn);
        for (int i =0 ;i<nn;i++) dad[i] = i; 
    }
    int find(int x) {
        if (x == dad[x]) return x;
        return dad[x] = find(dad[x]);
    }
    bool unite(int a,int b) {
        int x = find(a),y = find(b);
        if (x == y) return false;
        dad[x] = y;
        return true;
    }
} dsu;

vi x,y;
bool tryout(vector<pii> edgs) {
    int n = edgs.size();
    set<pii> benches[n];
    map<pii,vi> useful;
    for (int i = 0;i<n;i++) {
        auto it = edgs[i];
        pii p1 = {x[it.ff],y[it.ff]};
        pii p2 = {x[it.ss],y[it.ss]};
        if (p1.ff == p2.ff) {
            benches[i] = {{p1.ff-1,max(p1.ss,p2.ss)-1},{p1.ff+1,max(p1.ss,p2.ss)-1}};
        }
        else {
            benches[i] = {{max(p1.ff,p2.ff)-1,p1.ss-1},{max(p1.ff,p2.ff)-1,p1.ss+1}};
        }
        for (auto it : benches[i]) useful[it].push_back(i);
    }
    vi u(n),v(n),a(n,-1),b(n,-1);
    for (int i = 0;i<n;i++) u[i] = edgs[i].ff,v[i] = edgs[i].ss;
    set<int> ones,twos;
    for (int i = 0;i<n;i++) twos.insert(i);
    while (1) {
        if (ones.size()) {
            int fnd = *ones.begin();
            ones.erase(fnd);
            pii assign = *benches[fnd].begin();
            a[fnd] = assign.ff,b[fnd] = assign.ss;
            for (auto it : useful[assign]) {
                if (it == fnd) continue;
                if (big(benches[it]) == 2) ones.insert(it),twos.erase(it);
                else if (big(benches[it]) == 1) ones.erase(it);
                benches[it].erase(assign);
            }
            continue;
        }
        if (twos.empty()) break;
        int fnd = *twos.begin();
        twos.erase(fnd);
        pii assign = *benches[fnd].begin();
        a[fnd] = assign.ff,b[fnd] = assign.ss;
        for (auto it : useful[assign]) {
            if (it == fnd) continue;
            if (big(benches[it]) == 2) ones.insert(it),twos.erase(it);
            else if (big(benches[it]) == 1) ones.erase(it);
            benches[it].erase(assign);
        }
        continue;
    }
    for (int i = 0;i<n;i++) if (a[i] == -1 || b[i] == -1) return false;
    build(u,v,a,b);
    return true;
}

int construct_roads(std::vector<int> xx, std::vector<int> yy) {
    x = xx,y = yy;
    int n = x.size();
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }

    map<pii,int> id;
    for (int i = 0;i<n;i++) {
        id[{x[i],y[i]}] = i;
    }
    vi dx{2,0,-2,0},dy{0,2,0,-2};
    dsu = DSU(n);
    int con = 0;
    vector<pii> edgs;
    for (int i = 0;i<n;i++) {
        for (int j = 0;j<4;j++){
            if (id.count({x[i]+dx[j],y[i]+dy[j]})) {
                if (dsu.unite(i,id[{x[i]+dx[j],y[i]+dy[j]}])) {
                    con++;
                    edgs.push_back({i,id[{x[i]+dx[j],y[i]+dy[j]}]});
                }
            }
        }
    }
    if (con < n-1) return 0;
    if (tryout(edgs)) return 1;
    return 0;
}

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