Submission #1072627

#	Time	Username	Problem	Language	Result	Execution time	Memory
1072627		ewirlan	Fountain Parks (IOI21_parks)	C++17	100 / 100	1744 ms	93884 KiB

parks

//
#ifndef __SIZEOF_INT128__
  #define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
    string name{""};
    time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
    duration<float, std::milli> dur;
    Timer() = default;
    Timer(string nm): name(nm) {}
    ~Timer() {
        end = high_resolution_clock::now(); dur= end - start;
        cout << "@" << name << "> " << dur.count() << " ms" << '\n';
    }
};
template <typename T = int> inline T in()
{
    static T x;
    std::cin >> x;
    return x;
}
std::string yn(bool b)
{
    if(b) return "YES\n";
    else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
    for(const auto& i : wek)out << i << ' ';
    return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
    out << '{'<<par.first<<", "<<par.second<<"}";
    return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
#include "parks.h"
constexpr int maxn =2e5 + 3;
int rep[maxn];
int find(int w)
{
    if(!rep[w])return w;
    return rep[w] = find(rep[w]);
}
int uni_c(0);
void uni(int a, int b){
    a = find(a); b = find(b);
    if(a != b){
        rep[a] = b;
        ++uni_c;
    }
}
vector <pair <int, int>> graf[maxn];
bool byl[maxn];
int construct_roads(vector <int> x, vector <int> y)
{
    int n(sz(x));
    map <pair <int, int>, int> s;
    rep(i, 0, n)s[{x[i], y[i]}] = i+1;
    int m(0);
    map <pair <pair <int, int>, pair <int, int>>, int> k;
    vector <pair <pair <int, int>, pair <int, int>>> lk;
    vector <pair <int, int>> dld;
    rep(i, 0, n){
        if(s.count({x[i]+2, y[i]})){
            uni(i+1, s[{x[i]+2, y[i]}]);
            k[{{x[i],y[i]},{x[i]+2, y[i]}}] = ++m;
            lk.push_back({{x[i],y[i]},{x[i]+2, y[i]}});
            dld.pb(i, s[{x[i]+2, y[i]}]-1);
        }
        if(s.count({x[i], y[i]+2})){
            uni(i+1, s[{x[i], y[i]+2}]);
            k[{{x[i],y[i]},{x[i], y[i]+2}}] = ++m;
            lk.push_back({{x[i],y[i]},{x[i], y[i]+2}});
            dld.pb(i, s[{x[i], y[i]+2}]-1);
        }
    }
    if(uni_c != n-1)return 0;
    vector <pair <int, int>> v;
    map <pair <int, int>, int> nm;
    rep(i, 0, n) if(s.count({x[i]+2, y[i]}) && s.count({x[i], y[i]+2}) && s.count({x[i]+2, y[i]+2})){
        v.pb(x[i]+1, y[i]+1);
        nm[{x[i]+1, y[i]+1}] = sz(v);
    }
    rep(i, 0, sz(v)){
        auto [x, y] = v[i];
        if((x/2 + y/2) % 2){
            graf[i+1].pb(nm[{x-2, y}], k[{{x-1, y-1}, {x-1, y+1}}]);
            graf[i+1].pb(nm[{x+2, y}], k[{{x+1, y-1}, {x+1, y+1}}]);
            graf[nm[{x, y-2}]].pb(i+1, k[{{x-1, y-1}, {x+1, y-1}}]);
            graf[nm[{x, y+2}]].pb(i+1, k[{{x-1, y+1}, {x+1, y+1}}]);
        }
        else{
            graf[i+1].pb(nm[{x, y-2}], k[{{x-1, y-1}, {x+1, y-1}}]);
            graf[i+1].pb(nm[{x, y+2}], k[{{x-1, y+1}, {x+1, y+1}}]);
            graf[nm[{x-2, y}]].pb(i+1, k[{{x-1, y-1}, {x-1, y+1}}]);
            graf[nm[{x+2, y}]].pb(i+1, k[{{x+1, y-1}, {x+1, y+1}}]);
        }
    }
    // rep(i, 0, sz(v)+1)for(auto [j, kk]: graf[i])cout << (i ? v[i-1] : pair<int, int>{-1, -1} ) << ' ' << (j ? v[j-1] : pair<int, int>{-1,-1}) << ' ' << lk[kk-1] << '\n';
    stack <int> dfs; dfs.push(0);
    vector <bool> us(sz(lk));
    byl[0] = 1;
    while(dfs.size()){
        int w(dfs.top()); dfs.pop();
        for(auto [i, j]: graf[w])if(!byl[i]){
            byl[i] = 1;
            dfs.push(i);
            us[j-1] = 1;
        }
    }
    vector <int> ru, rv, ra, rb;
    rep(i, 0, sz(lk))if(!us[i]){
        auto [a, b] = dld[i];
        ru.pb(a);
        rv.pb(b);
        if(x[a] == x[b]){
            if((x[a]/2 + y[a]/2) % 2){
                ra.pb(x[a]-1);
                rb.pb(y[a]+1);
            }
            else{
                ra.pb(x[a]+1);
                rb.pb(y[a]+1);

            }
        }
        else{
            if((x[a]/2 + y[a]/2) % 2){
                ra.pb(x[a]+1);
                rb.pb(y[a]+1);
            }
            else{
                ra.pb(x[a]+1);
                rb.pb(y[a]-1);

            }
        }
    }
    build(ru, rv, ra, rb);
    return 1;
}

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