Submission #439964

#	Time	Username	Problem	Language	Result	Execution time	Memory
439964		cheeheng	Fountain Parks (IOI21_parks)	C++17	0 / 100	47 ms	83240 KiB

parks

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

typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;

const int dx[] = {-1,0,0,1};
const int dy[] = {0,1,-1,0};

vector<int> AdjList[200005];
ii EdgeList[800005];
ii EdgeList2[800005];
map<ii, int> indx;
map<ii, int> indxEdge;
map<ii, int> indxBench;

vector<int> AdjListBench[800005];
set<int> AdjListRoad[200005];
int degBench[800005];
ii benchXY[800005];

struct Dinic{
    static const int MAX_E = 1000005;
    static const int MAX_V = 1000005;

    // Edge List
    ii EdgeList[MAX_E<<1];
    int flow[MAX_E<<1];
    int capacity[MAX_E<<1];

    vector<int> AdjList[MAX_V];
    int level[MAX_V];
    int ptr[MAX_V];

    int E = 0;

    int s, t;

    Dinic(int _s, int _t){
        s = _s;
        t = _t;
    }

    void add_edge(int u, int v, int c){
        EdgeList[E] = ii(u, v);
        EdgeList[E+1] = ii(v, u);
        flow[E] = 0;
        flow[E+1] = 0;
        capacity[E] = c;
        capacity[E+1] = 0;

        AdjList[u].push_back(E);
        AdjList[v].push_back(E+1);

        E += 2;
    }

    bool bfs(){
        memset(level, -1, sizeof(level));
        queue<int> q;
        level[s] = 0;
        q.push(s);
        while(!q.empty()){
            int u = q.front(); q.pop();
            for(int indx: AdjList[u]){
                int v = EdgeList[indx].second;
                if(level[v] == -1 && capacity[indx] > flow[indx]){
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[t] != -1;
    }

    int dfs(int u, int flowToSend){
        if(u == t){return flowToSend;}
        if(flowToSend == 0){return 0;}

        while(ptr[u] < (int)AdjList[u].size()){
            int indx = AdjList[u][ptr[u]];
            int v = EdgeList[indx].second;
            if(capacity[indx] > flow[indx] && level[v] == level[u] + 1){
                int nxtFlow = min(flowToSend, capacity[indx] - flow[indx]);
                int flowSent = dfs(v, nxtFlow);
                if(flowSent > 0){
                    flow[indx] += flowSent; // flow from u to v
                    flow[indx^1] -= flowSent; // flow from v to u
                    return flowSent;
                }
            }
            ptr[u] ++;
        }
        return 0;
    }

    int findMaxFlow(){
        int maxFlow = 0;
        while(1){
            if(!bfs()){return maxFlow;}

            memset(ptr, 0, sizeof(ptr));
            while(1){
                int temp = dfs(s, INT_MAX);
                maxFlow += temp;
                if(temp == 0){break;}
            }
        }
    }
};

struct UnionFind{
    vector<int> p;
    vector<int> rank1;
    void init(int n){
        p.assign(n, 0);
        rank1.assign(n, 0);
        for(int i = 0; i < n; i ++){
            p[i] = i;
            rank1[i] = 0;
        }
    }

    int findSet(int i){
        return (p[i] == i) ? i : (p[i] = findSet(p[i]));
    }

    bool isSameSet(int i, int j){
        return findSet(i) == findSet(j);
    }

    void unionSet(int i, int j){
        int x = findSet(i);
        int y = findSet(j);

        if(x != y){
            if(rank1[x] > rank1[y]){
                p[y] = x;
            }else{
                p[x] = y;
                if(rank1[x] == rank1[y]){
                    rank1[y] ++;
                }
            }
        }
    }
};

int p[200005];

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

    vector<int> U(n-1);
    vector<int> V(n-1);
    vector<int> A(n-1);
    vector<int> B(n-1);

    for(int i = 0; i < n; i ++){
        indx[ii(x[i], y[i])] = i;
    }

    int cnt3 = 0;
    for(pair<ii, int> temp: indx){
        p[cnt3 ++] = temp.second;
    }

    int m = 0;
    for(int i = 0; i < n; i ++){
        int i2 = p[i];
        for(int k = 0; k < 4; k ++){
            int nx = x[i2] + 2*dx[k];
            int ny = y[i2] + 2*dy[k];

            if(indx.find(ii(nx, ny)) != indx.end()){
                int j = indx[ii(nx, ny)];
                EdgeList[m ++] = ii(i2, j);
            }
        }
    }

    UnionFind* uf = new UnionFind();
    uf->init(n);

    int cnt = 0;
    for(int i = 0; i < m; i ++){
        int u, v;
        tie(u, v) = EdgeList[i];
        if(!uf->isSameSet(u, v)){
            uf->unionSet(u, v);
            AdjList[u].push_back(v);
            AdjList[v].push_back(u);
            EdgeList2[cnt] = ii(u, v);
            indxEdge[ii(u, v)] = cnt;
            cnt ++;
        }
    }

    if(cnt != n-1){
        return 0;
    }

    int benches = 0;
    memset(degBench, 0, sizeof(degBench));
    for(int i = 0; i < n-1; i ++){
        int u, v;
        tie(u, v) = EdgeList2[i];
        int x2 = (x[u] + x[v])/2;
        int y2 = (y[u] + y[v])/2;

        for(int k = 0; k < 4; k ++){
            int nx = x2 + dx[k];
            int ny = y2 + dy[k];
            if(nx%2 == 1 && ny%2 == 1){
                int indx2 = benches;
                if(indxBench.find(ii(nx, ny)) != indxBench.end()){
                    indx2 = indxBench[ii(nx, ny)];
                }else{
                    benchXY[benches] = ii(nx, ny);
                    indxBench[ii(nx, ny)] = benches;
                    //printf("bench %d; (%d, %d)\n", benches, nx, ny);
                    benches ++;
                }

                AdjListBench[indx2].push_back(i);
                AdjListRoad[i].insert(indx2);
                //printf("road %d; bench %d\n", i, indx2);
                degBench[i] ++;
            }
        }
    }

    int S = n+benches;
    int T = n+benches+1;
    Dinic* mf = new Dinic(S, T);

    for(int i = 0; i < n; i ++){
        mf->add_edge(S, i, 1);
    }

    for(int i = 0; i < benches; i ++){
        mf->add_edge(n+i, T, 1);
    }

    for(int i = 0; i < n; i ++){
        for(int j: AdjListBench[i]){
            mf->add_edge(i, n+j, 1);
        }
    }

    int res = mf->findMaxFlow();
    //printf("res=%d\n", res);
    assert(res == n-1);

    int cnt2 = 0;
    for(int i = 0; i < mf->E; i ++){
        int u, v;
        tie(u, v) = mf->EdgeList[i];
        //printf("u=%d v=%d\n", u, v);
        if(u >= n){continue;}

        if(mf->flow[i] > 0){
            tie(U[cnt2], V[cnt2]) = EdgeList2[u];
            tie(A[cnt2], B[cnt2]) = benchXY[v-n];
            cnt2 ++;
        }
    }

    assert(cnt2 == n-1);

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

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