Submission #813586

#	Time	Username	Problem	Language	Result	Execution time	Memory
813586		Username4132	Fountain Parks (IOI21_parks)	C++17	70 / 100	530 ms	135620 KiB

parks

#include "parks.h"
#include <iostream>
#include <vector>
#include<map>
#include<algorithm>
#include<cassert>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
#define F first
#define S second
#define MP make_pair

const int MAXN = 400010;
int n, eind, bi, curi, X[MAXN], Y[MAXN];
bool vis1[MAXN], vis2[MAXN], vis3[MAXN];
pii ptsInd[MAXN];
map<pii, int> mp;
map<pii, int> ben;
vector<pii> g1[MAXN], draw;
vector<int> g2[MAXN];
vector<int> g3[MAXN];
pii nam[MAXN];

int getInd(pii b){
    auto itr = ben.find(b);
    if(itr!=ben.end()) return itr->S;
    else{
        ben[b]=bi;
        ptsInd[bi]=b;
        ++bi;
        return bi-1;
    }
}

void sed(int u, int v){
    int ind = curi++;
    nam[ind] = {u, v};
    int ux = X[u], uy = Y[u];
    int vx = X[v], vy = Y[v];

    if(ux==vx){
        if(uy>vy) swap(uy, vy);
        int i = getInd({ux-1, uy+1});
        int j = getInd({ux+1, uy+1});
        g2[ind].PB(i), g2[ind].PB(j);
        g3[i].PB(ind), g3[j].PB(ind);
    }
    else{
        if(ux>vx) swap(ux, vx);
        int i = getInd({ux+1, uy-1});
        int j = getInd({ux+1, uy+1});
        g2[ind].PB(i), g2[ind].PB(j);
        g3[i].PB(ind), g3[j].PB(ind);
    }

}

void dfs1(int v){
    vis1[v]=true;
    for(pii to:g1[v]) if(!vis1[to.F]){
        sed(v, to.F);
        dfs1(to.F);
    }

}

void dfs2(int v, bool flag){
    if(!flag){
        vis2[v]=true;
        int cn = 0;
        for(int to:g2[v]) if(!vis3[to]){
            if(!cn) draw.PB({v, to});
            dfs2(to, !flag);
            ++cn;
        }
    }
    else{
        vis3[v]=true;
        for(int to:g3[v]) if(!vis2[to]) dfs2(to, !flag);
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    n = (int)x.size();
    forn(i, n){
        mp[MP(x[i], y[i])] = i;
        X[i]=x[i];
        Y[i]=y[i];
    }

    for(auto el:mp){
        auto it = mp.find(MP(el.F.F + 2, el.F.S));
        if(it!=mp.end()){
            g1[el.S].PB(MP(it->S, eind));
            g1[it->S].PB(MP(el.S, eind));
            ++eind;
        }
        it = mp.find({el.F.F, el.F.S + 2});
        if(it!=mp.end()){
            g1[el.S].PB(MP(it->S, eind));
            g1[it->S].PB(MP(el.S, eind));
            ++eind;
        }
    }


    dfs1(0);

    bool possible=true;
    forn(i, n) possible&=vis1[i];
    if(!possible){
        return 0;
    }

    forn(el, curi) if(!vis2[el]) dfs2(el, false);

    vector<int> u, v, a, b;

    for(pii el:draw){
        u.PB(nam[el.F].F);
        v.PB(nam[el.F].S);
        a.PB(ptsInd[el.S].F);
        b.PB(ptsInd[el.S].S);
    }

    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