Submission #621340

#	Time	Username	Problem	Language	Result	Execution time	Memory
621340		Bench0310	Fountain Parks (IOI21_parks)	C++17	100 / 100	1939 ms	92860 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"

using namespace std;
typedef long long ll;

int construct_roads(vector<int> x,vector<int> y)
{
    int n=x.size();
    map<array<int,2>,int> id;
    for(int i=0;i<n;i++) id[{x[i],y[i]}]=i;
    map<array<int,2>,int> bench_id;
    int m=0;
    auto fountain_pos=[&](int a,int b)->int{return (id.find({a,b})!=id.end()?id[{a,b}]:-1);};
    auto tp=[&](int a,int b)->int{return (((a+b)/2)&1);}; //color of chessboard at this bench
    for(int i=0;i<n;i++)
    {
        int a=x[i],b=y[i];
        if(fountain_pos(a+2,b)!=-1&&fountain_pos(a,b+2)!=-1&&fountain_pos(a+2,b+2)!=-1)
        {
            bench_id[{a+1,b+1}]=(++m);
        }
    }
    auto bench_pos=[&](int a,int b)->int{return (bench_id.find({a,b})!=bench_id.end()?bench_id[{a,b}]:0);};
    vector<array<int,3>> g[m+1]; //to,bad_a,bad_b
    for(auto [p,bench]:bench_id)
    {
        auto [a,b]=p;
        if(tp(a,b)==0)
        {
            for(int dy:{-2,2})
            {
                int t=bench_pos(a,b+dy);
                g[t].push_back({bench,fountain_pos(a-1,b+dy/2),fountain_pos(a+1,b+dy/2)});
            }
        }
        else
        {
            for(int dx:{-2,2})
            {
                int t=bench_pos(a+dx,b);
                g[t].push_back({bench,fountain_pos(a+dx/2,b-1),fountain_pos(a+dx/2,b+1)});
            }
        }
    }
    set<array<int,2>> bad_edges;
    vector<bool> vis(m+1,0);
    function<void(int)> dfs=[&](int a)
    {
        vis[a]=1;
        for(auto [to,bad_a,bad_b]:g[a])
        {
            if(!vis[to])
            {
                bad_edges.insert({bad_a,bad_b});
                bad_edges.insert({bad_b,bad_a});
                dfs(to);
            }
        }
    };
    dfs(0);
    vector<int> p(n);
    for(int i=0;i<n;i++) p[i]=i;
    vector<int> sz(n,1);
    int cc=n;
    function<int(int)> find_set=[&](int a)->int
    {
        if(a==p[a]) return a;
        else return p[a]=find_set(p[a]);
    };
    auto merge_sets=[&](int a,int b)->bool
    {
        a=find_set(a);
        b=find_set(b);
        if(a==b) return 0;
        if(sz[a]<sz[b]) swap(a,b);
        p[b]=a;
        sz[a]+=sz[b];
        cc--;
        return 1;
    };
    vector<int> ru,rv,ra,rb;
    for(int i=0;i<n;i++)
    {
        int a=x[i],b=y[i];
        //horizontal
        for(int dx:{2})
        {
            int j=fountain_pos(a+dx,b);
            if(j==-1||bad_edges.find({i,j})!=bad_edges.end()) continue;
            if(merge_sets(i,j))
            {
                ru.push_back(i);
                rv.push_back(j);
                int d=(tp(a+1,b+1)==0?1:-1);
                ra.push_back(a+1);
                rb.push_back(b+d);
            }
        }
        //vertical
        for(int dy:{2})
        {
            int j=fountain_pos(a,b+dy);
            if(j==-1||bad_edges.find({i,j})!=bad_edges.end()) continue;
            if(merge_sets(i,j))
            {
                ru.push_back(i);
                rv.push_back(j);
                int d=(tp(a+1,b+1)==1?1:-1);
                ra.push_back(a+d);
                rb.push_back(b+1);
            }
        }
    }
    if(cc==1) build(ru,rv,ra,rb);
    return (cc==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