Submission #1217737

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217737		guagua0407	Fountain Parks (IOI21_parks)	C++20	45 / 100	285 ms	41944 KiB

parks

#include "parks.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

namespace{
    struct DSU{
        vector<int> e;
        DSU(int n){
            e=vector<int>(n,-1);
        }
        int find(int x){
            return (e[x]<0?x:e[x]=find(e[x]));
        }
        int sz(int x){
            return -e[find(x)];
        }
        bool unite(int a,int b){
            a=find(a);
            b=find(b);
            if(a==b) return false;
            if(e[a]>e[b]) swap(a,b);
            e[a]+=e[b];
            e[b]=a;
            return true;
        }
    };
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    map<int,map<int,int>> mp;
    int n=(int)x.size();
    for(int i=0;i<n;i++){
        mp[y[i]][x[i]]=i+1;
    }
    vector<int> u,v,a,b;
    for(int i=0;i<n;i++){
        if(mp[y[i]+2][x[i]]!=0){
            u.push_back(i);
            v.push_back(mp[y[i]+2][x[i]]-1);
            if((x[i]+y[i])%4==0){
                a.push_back(x[i]-1);
                b.push_back(y[i]+1);
            }
            else{
                a.push_back(x[i]+1);
                b.push_back(y[i]+1);
            }
        }
        if(mp[y[i]][x[i]+2]!=0){
            u.push_back(i);
            v.push_back(mp[y[i]][x[i]+2]-1);
            if((x[i]+y[i])%4==0){
                a.push_back(x[i]+1);
                b.push_back(y[i]+1);
            }
            else{
                a.push_back(x[i]+1);
                b.push_back(y[i]-1);
            }
        }
    }
    DSU dsu(n);
    for(int i=0;i<(int)u.size();i++){
        dsu.unite(u[i],v[i]);
    }
    if(dsu.sz(0)!=n) return 0;
    build(u,v,a,b);
    return 1;
}

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