Submission #435539

#	Time	Username	Problem	Language	Result	Execution time	Memory
435539		Ozy	Fountain Parks (IOI21_parks)	C++17	15 / 100	1578 ms	84124 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define MAX 200000
#define fil first
#define col second

int n,num;
vector<int> u,v,a,b;
set<pair<int,int> > existe;
map<pair<int,int>,int> id;
map<int,pair<int,int> > val;
vector< int > hijos[MAX+2];
int visitados[MAX+2],ori[8] {2,0,-2,0,0,2,0,-2};

void DFS(int pos) {

    visitados[pos] = 1;
    num++;
    existe.erase(val[pos]);

    for (auto h : hijos[pos]) {
        pair<int,int> p = val[pos];
        pair<int,int> q = val[h];
        if (existe.find(q) == existe.end()) continue;

        if (p.fil == q.fil){
            u.push_back(pos);
            v.push_back(h);
            a.push_back(min(p.col,q.col)+1); //columna
            b.push_back(p.fil-1);
        }
        else {
            u.push_back(pos);
            v.push_back(h);
            b.push_back(min(p.fil, q.fil)+1);
            if (p.col == 2) a.push_back(1);
            else a.push_back(5);
        }
    }

    for (auto h : hijos[pos]) if (visitados[h] == 0) DFS(h);

}

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

    n = x.size();
    rep(i,0,n) {
        existe.insert({y[i], x[i]});
        id[{y[i], x[i]}] = i;
        val[i] = {y[i], x[i]};

        rep(j,0,3) {
            if (existe.find({y[i]+ori[j], x[i]+ori[j+4]}) != existe.end()) {
                hijos[i].push_back(id[{y[i]+ori[j], x[i]+ori[j+4]}]);
                hijos[id[{y[i]+ori[j], x[i]+ori[j+4]}]].push_back(i);
            }
        }
    }

    DFS(0);
    if (num < n) return 0;

    build(u, v, a, b);
    return 1;
}

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