Submission #602979

#	Time	Username	Problem	Language	Result	Execution time	Memory
602979		2fat2code	Fountain Parks (IOI21_parks)	C++17	5 / 100	373 ms	47424 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 200005;

int n, par[nmax];
vector<pair<int,int>>vertex;
map <pair<int,int>, int>varfuri, banci;
vector<int>u, v, assigned_a, assigned_b;

int findpar(int x){
    if(x != par[x]){
        par[x] = findpar(par[x]);
    }
    return par[x];
}

void join(int x, int y){
    x = findpar(x);
    y = findpar(y);
    par[x] = y;
}

int construct_roads(vector<int> x, vector<int> y) {
    n = (int)x.size();
    for(int i=0;i<n;i++){
        vertex.push_back({x[i], y[i]});
        varfuri[{x[i], y[i]}] = i;
    }
    sort(all(vertex));
    for(auto it : vertex){
        if(varfuri.count({it.fr - 2, it.sc})){
            if(it.fr % 4 == 0){
                if(it.sc % 4 == 2){
                    if(!banci.count({it.fr - 1, it.sc - 1})){
                        banci[{it.fr-1, it.sc-1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr - 2, it.sc}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
                else{
                    if(!banci.count({it.fr - 1, it.sc + 1})){
                        banci[{it.fr-1, it.sc + 1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr - 2, it.sc}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc + 1);
                    }
                }
            }
            else{
                if(it.sc % 4 == 2){
                    if(!banci.count({it.fr - 1, it.sc + 1})){
                        banci[{it.fr-1, it.sc+1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr - 2, it.sc}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc + 1);
                    }
                }
                else{
                    if(!banci.count({it.fr - 1, it.sc - 1})){
                        banci[{it.fr-1, it.sc-1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr - 2, it.sc}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
            }
        }
        if(varfuri.count({it.fr, it.sc - 2})){
            if(it.fr % 4 == 0){
                if(it.sc % 4 == 2){
                    if(!banci.count({it.fr - 1, it.sc + 1})){
                        banci[{it.fr-1, it.sc+1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr, it.sc - 2}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc + 1);
                    }
                }
                else{
                    if(!banci.count({it.fr - 1, it.sc - 1})){
                        banci[{it.fr-1, it.sc - 1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr, it.sc - 2}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
            }
            else{
                if(it.sc % 4 == 2){
                    if(!banci.count({it.fr - 1, it.sc - 1})){
                        banci[{it.fr-1, it.sc-1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr, it.sc - 2}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
                else{
                    if(!banci.count({it.fr + 1, it.sc - 1})){
                        banci[{it.fr+1, it.sc-1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr, it.sc - 2}]);
                        assigned_a.push_back(it.fr + 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
            }
        }
    }
    for(int i=0;i<n;i++) par[i] = i;
    for(int i=0;i<(int)u.size();i++){
        join(u[i], v[i]);
    }
    for(int i=0;i<n;i++){
        findpar(i);
    }
    for(int i=0;i<n-1;i++){
        if(par[i] != par[i + 1]) return 0;
    }
    build(u, v, assigned_a, assigned_b);
    return 1;
}

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