Submission #464972

#	Time	Username	Problem	Language	Result	Execution time	Memory
464972		peti1234	Fountain Parks (IOI21_parks)	C++17	100 / 100	910 ms	55248 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
using namespace std;

/*
void build(vector<int> a, vector<int> b, vector<int> c, vector<int> d) {
    for (int i=0; i<a.size(); i++) {
        cout << a[i] << " " << b[i] << " " << c[i] << " " << d[i] << "\n";
    }
    return;
}
*/
const int c=200005;
int ki[c], n, cnt;
map<pair<int, int>, int> m;
set<pair<int, int> > s;
vector<int> ans[4];
int ert(int a, int b) {
    if (m.find({a, b})!=m.end()) {
        return m[{a, b}];
    }
    return 0;
}
int holvan(int a) {
    return (ki[a] ? ki[a]=holvan(ki[a]) : a);
}
void unio(int a, int b) {
    a=holvan(a), b=holvan(b);
    if (a!=b) {
        ki[a]=b;
        cnt++;
    }
}
void add(int a, int b, pair<int, int> c) {
    unio(a, b);
    ans[0].push_back(a-1), ans[1].push_back(b-1), ans[2].push_back(c.first), ans[3].push_back(c.second);
}

int construct_roads(vector<int> a, vector<int> b) {
    n=a.size();
    for (int i=0; i<n; i++) {
        int x=a[i], y=b[i];
        m[{x, y}]=i+1;
        s.insert({x-1, y-1}), s.insert({x-1, y+1}), s.insert({x+1, y-1}), s.insert({x+1, y+1});
    }
    for (auto p:s) {
        int x=p.first, y=p.second;
        int a=ert(x-1, y-1), b=ert(x-1, y+1), c=ert(x+1, y-1), d=ert(x+1, y+1), aa=0, bb=0;
        /*cout << x << " " << y << " " << a << " " << b << " " << c << " " << d << "\n";
        if (x==-1 && y==1) {
            cout << "fontos " << x+1 << " " << y+1 << " " << ert(x+1, y+1) << "\n";
        }*/
        bool s=(x+y)%4;

        if (s && !aa && a && b) aa=a, bb=b;
        if (s && !aa && c && d) aa=c, bb=d;

        if (!s && !aa && a && c) aa=a, bb=c;
        if (!s && !aa && b && d) aa=b, bb=d;

        if (aa) {
            add(aa, bb, p);
        }
    }
    if (cnt==n-1) {
        build(ans[0], ans[1], ans[2], ans[3]);
    }
    return (cnt==n-1);
}


/*

int main()
{
    int n;
    vector<int> a, b;
    cin >> n;
    for (int i=1; i<=n; i++) {
        int x, y;
        cin >> x >> y;
        a.push_back(x), b.push_back(y);
    }
    int x=construct_roads(a, b);
    cout << x << "\n";
    return 0;
}
*/
/*
2
0 0
0 2
*/

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