Submission #1223156

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223156		CELD_07	Fountain Parks (IOI21_parks)	C++20	15 / 100	375 ms	39584 KiB

parks

#include "parks.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={2, 0};
ll dy[]={0, 2};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
vector<ll> s, p;
inline ll _find(ll a){
if(a!=p[a]){p[a]=_find(p[a]);return p[a];}
return a;
}
inline void _union(ll a, ll b){
a=_find(a);
b=_find(b);
if(a==b)return;
if(s[a]<s[b])swap(a, b);
s[a]+=s[b];
p[b]=a;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
vector<ll>().swap(s);
vector<ll>().swap(p);
s.assign(x.size()+1, 1);
p.resize(x.size()+1);
for(int i=0; i<x.size(); i++)p[i]=i;
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    map<pair<ll, ll>, ll> m;
    vector<int> u, v, a, b;
    ll cnt=0;
    for(int i=0; i<x.size(); i++)m[{x[i], y[i]}]=i+1;
    for(int i=0; i<x.size(); i++){
     for(int j=0; j<2; j++){
     ll nx=x[i]+dx[j], ny=y[i]+dy[j];
     if(m[{nx, ny}]==0)continue;
     if(nx==4 && x[i]==2){
     u.push_back(m[{nx, ny}]-1);
     v.push_back(i);
     _union(m[{nx, ny}]-1, i);
     a.push_back(3);
     b.push_back(y[i]-1);
     cnt++;
     }else if(nx==2 && x[i]==2){
     u.push_back(m[{nx, ny}]-1);
     v.push_back(i);
     _union(m[{nx, ny}]-1, i);
     a.push_back(1);
     b.push_back(y[i]+1);
     cnt++;
     }else if(nx==4 && x[i]==4){
     u.push_back(m[{nx, ny}]-1);
     v.push_back(i);
     _union(m[{nx, ny}]-1, i);
     a.push_back(5);
     b.push_back(y[i]+1);
     cnt++;
     }
     }
    }
    if(s[_find(0)]==x.size()){build(u, v, a, b);return 1;}
    return 0;
}

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