Submission #498297

#	Time	Username	Problem	Language	Result	Execution time	Memory
498297		thomas_li	Fountain Parks (IOI21_parks)	C++17	0 / 100	0 ms	204 KiB

parks

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;

void build(vector<int> u,vector<int> v, vector<int> a, vector<int> b);

void mbuild(vector<int> u,vector<int> v, vector<int> a, vector<int> b){
    int m = u.size();
    for(int i = 0; i < m; i++){
        cout << u[i] << " " << v[i] << " " << a[i] << " " << b[i] << "\n";
    }
}
int construct_roads(vector<int> sus, vector<int> amongus){
    set<array<int,3>> a; set<array<int,2>> used;
    int n = sus.size();
    vector<int> par(n),sz(n,1); int cnt = n;
    for(int i = 0; i < n; i++) a.insert({sus[i],amongus[i],i}),par[i] = i;
    auto has = [&](int x, int y){
        auto itr = a.lower_bound({x,y,-1});
        if(itr == a.end()) return -1;
        return (*itr)[2];
    };
    auto find = [&](int x){
        while(x != par[x]){
            par[x] = par[par[x]];
            x = par[x];
        }
        return x;
    };
    auto join = [&](int x, int y){
        x = find(x); y = find(y);
        if(x == y) return false;
        if(sz[x] > sz[y]) swap(x,y);     
        sz[y] += sz[x];
        cnt--;
        par[x] = y;
        return true;
    };
    vector<int> u,v,ba,bb;
    auto add_sol = [&](int i, int j, int x, int y){ // connect fountain i and j with (x,y) bench
        u.emplace_back(i); v.emplace_back(j);
        used.insert({x,y});
        ba.emplace_back(x); bb.emplace_back(y);
    };
    for(auto[x,y,i] : a){
        int p;
        if((p = has(x+2,y)) != -1){
            if(find(i) != find(p)){
                if((x+y) % 4 == 0){
                    join(i,p);   
                    add_sol(i,p,x+1,y+1);
                } else if(used.find({x+1,y-1}) == used.end()){
                    join(i,p);
                    add_sol(i,p,x+1,y-1);
                }
            }  
        }
        if((p = has(x,y+2)) != -1){
            if(find(i) != find(p)){
                if((x+y) % 4 != 0){
                    join(i,p);   
                    add_sol(i,p,x+1,y+1);
                } else if(used.find({x-1,y+1}) == used.end()){
                    join(i,p);
                    add_sol(i,p,x-1,y+1);
                }
            }  
        }
    }
    if(cnt != 1) return 0;
    build(u,v,ba,bb); 
    //mbuild(u,v,ba,bb); 
    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