Submission #1062264

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062264		mariaclara	Fountain Parks (IOI21_parks)	C++17	15 / 100	416 ms	89184 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MAX = 2e5+5;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second

int N;
vector<int> v[MAX], X, Y;
vector<pii> range[MAX];

bool check(vector<pii> e) {
    vector<int> g[N];

    for(auto [A,B] : e) 
        g[A].pb(B), g[B].pb(A);

    queue<int> fila;
    vector<bool> vis(N);
    fila.push(0);
    vis[0] = 1;

    while(!fila.empty()) {
        int at = fila.front();
        fila.pop();

        for(int viz : g[at])
            if(!vis[viz]) fila.push(viz), vis[viz] = 1;
    }

    for(int i = 0; i < N; i++) if(!vis[i]) return 0;
    return 1;
}

void construct(vector<pii> edges){
    vector<int> U, V, A, B;
    map<pii,vector<pii>> point;

    // vamos anotar pontos e quantas ruas eles olham

    for(auto [i1, i2] : edges){
        int x1 = X[i1], y1 = Y[i1], x2 = X[i2], y2 = Y[i2];
        if(x1 == x2) {
            point[{x1+1, (y1+y2)/2}].pb({i1,i2});
            point[{x1-1, (y1+y2)/2}].pb({i1,i2});
        }
        if(y1 == y2) {
            point[{(x1+x2)/2, y1+1}].pb({i1,i2});
            point[{(x1+x2)/2, y1-1}].pb({i1,i2});
        }
    }

    queue<pii> fila;

    for(auto [p, qtd] : point)
        if(sz(qtd) == 1) fila.push(p);

    while(!point.empty()) {
        if(fila.empty()) fila.push((*point.begin()).fr);

        auto [a,b] = fila.front();
        fila.pop();

        if(point.count({a,b}) == 0) continue;
        auto [u,v] = point[{a,b}].back();
        point[{a,b}].pop_back();

        U.pb(u); V.pb(v); A.pb(a); B.pb(b);

        pii p = {a,b};
        if(X[u] == X[v]) p.fr = 2*X[u] - p.fr;
        else p.sc = 2*Y[u] - p.sc;

        for(int ind = 0; ind < sz(point[p]); ind++) {
            if(point[p][ind] == mk(u,v)) {
                point[p].erase(point[p].begin() + ind);
                break;
            }
        }

        if(point[p].empty()) point.erase(p);
        if(point[{a,b}].empty()) point.erase({a,b});
    }

    build(U, V, A, B);
}

int construct_roads(vector<int> x, vector<int> y) {
    N = sz(x);
    map<pii,int> ind;
    X = x;
    Y = y;

    for(int i = 0; i < N; i++)
        ind[{x[i], y[i]}] = i, v[x[i]].pb(y[i]);

    vector<pii> edges;

    for(int i = 2; i < MAX; i += 2) {
        sort(all(v[i]));
        for(int k = 0, last = -1; k < sz(v[i]); k++) {
            int j = v[i][k];
            // olhando o ponto (i,j)

            if(last == -1) last = j;
            if(k+1 == sz(v[i]) or v[i][k+1] - j != 2) range[i].pb({last, j}), last = -1;
            else edges.pb({ind[{i, j}], ind[{i, j+2}]});
        }
    }

    for(int i = 2; i < MAX; i += 2) {
        for(int j = 0, k = 0; j < sz(range[i]) and k < sz(range[i-2]); ) {
            if(range[i][j].sc < range[i-2][k].fr) j++;
            else if(range[i-2][k].sc < range[i][j].fr) k++;
            else {
                int p = min(range[i][j].sc, range[i-2][k].sc);
                edges.pb({ind[{i-2,p}], ind[{i,p}]});
                if(range[i][j].sc < range[i-2][k].sc) j++;
                else k++;
            }
        }
    }

    if(!check(edges)) return 0;

    construct(edges);
    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