Submission #481733

#	Time	Username	Problem	Language	Result	Execution time	Memory
481733		Fysty	Fountain Parks (IOI21_parks)	C++17	45 / 100	627 ms	59960 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
const int MOD2=998244353;
const ll INF=3e18;
const ld PI=3.14159265358979323846;
ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);}
ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll ans=fpow(a*a%m,b/2,m);
    return (b%2?ans*a%m:ans);
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
//#define int ll
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define repk(i,m,n) for(int i=m;i<n;i++)
#define F first
#define S second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)
const int N=2e5+1;
bool vis[N<<2];
vector<int> x,y;
vector<int> retu,retv,a,b;
vector<pii> ed[N<<2];
pii point[N],pos[N<<2];
set<pii> edges;
map<pii,int> id,id2;
int n,tn=0,cnt=0;
int par[N];
int fp(int u){return u==par[u]?u:par[u]=fp(par[u]);}
int unite(int u,int v)
{
    if(fp(u)==fp(v)) return 0;
    par[fp(v)]=fp(u);
    return 1;
}

/*void build(vector<int> v1,vector<int> v2,vector<int> v3,vector<int> v4)
{
    for(ll u:v1) cout<<u<<" ";
    cout<<"\n";
    for(ll u:v2) cout<<u<<" ";
    cout<<"\n";
    for(ll u:v3) cout<<u<<" ";
    cout<<"\n";
    for(ll u:v4) cout<<u<<" ";
    cout<<"\n";
}
*/
void solve()
{
    for(pii tmp:edges)
    {
        int u=tmp.F,v=tmp.S;
        int can=unite(u,v);
        if(can)
        {
            cnt++;
            retu.pb(u);
            retv.pb(v);
            if(y[u]==y[v])
            {
                int mid=(x[u]+x[v])>>1;
                if((mid+y[u]+1)%4==0)
                {
                    a.pb(mid);
                    b.pb(y[u]+1);
                }
                else
                {
                    a.pb(mid);
                    b.pb(y[u]-1);
                }
            }
            else
            {
                int mid=(y[u]+y[v])>>1;
                if((mid+x[u]+1)%4==2)
                {
                    a.pb(x[u]+1);
                    b.pb(mid);
                }
                else
                {
                    a.pb(x[u]-1);
                    b.pb(mid);
                }
            }
            //if(b.back()<2) {dbg(u,v,b.back());}
        }
    }
}
void dfs(int u)
{
    vis[u]=1;
    for(pii tmp:ed[u])
    {
        if(vis[tmp.F]) continue;
        pii p=pos[tmp.F];
        if(tmp.S==1)
        {
            edges.erase({id[{p.F+1,p.S-1}],id[{p.F+1,p.S+1}]});
            edges.erase({id[{p.F+1,p.S+1}],id[{p.F+1,p.S-1}]});
        }
        else if(tmp.S==2)
        {
            edges.erase({id[{p.F-1,p.S-1}],id[{p.F-1,p.S+1}]});
            edges.erase({id[{p.F-1,p.S+1}],id[{p.F-1,p.S-1}]});
        }
        else if(tmp.S==3)
        {
            edges.erase({id[{p.F-1,p.S-1}],id[{p.F+1,p.S-1}]});
            edges.erase({id[{p.F+1,p.S-1}],id[{p.F-1,p.S-1}]});
        }
        else if(tmp.S==4)
        {
            edges.erase({id[{p.F-1,p.S+1}],id[{p.F+1,p.S+1}]});
            edges.erase({id[{p.F+1,p.S+1}],id[{p.F-1,p.S+1}]});
        }
        dfs(tmp.F);
    }
}
int construct_roads(vector<int> X,vector<int> Y) {
    x=X;
    y=Y;
    n=x.size();
    if(n==1)
	{
	    build(retu,retv,a,b);
        return 1;
    }
    rep(i,n)
    {
        point[i]={x[i],y[i]};
        id[point[i]]=i;
    }
    rep(i,n)
    {
        int tmp=0;
        if(id.count({x[i]+2,y[i]}))
        {
            edges.insert({id[{x[i]+2,y[i]}],i});
            tmp++;
        }
        if(id.count({x[i],y[i]+2}))
        {
            edges.insert({id[{x[i],y[i]+2}],i});
            tmp++;
        }
        if(tmp==2)
        {
            if(id.count({x[i]+2,y[i]+2}))
            {
                tn++;
                pos[tn]={x[i]+1,y[i]+1};
                id2[{x[i]+1,y[i]+1}]=tn;
            }
        }
    }
    rep1(i,tn)
    {
        pii tmp=pos[i];
        if((tmp.F+tmp.S)%4==0)
        {
            if(id2.count({tmp.F,tmp.S-2}))
            {
                int u=id2[{tmp.F,tmp.S-2}];
                ed[i].pb({u,4});
                ed[u].pb({i,3});
            }
            else ed[0].pb({i,3});
            if(id2.count({tmp.F,tmp.S+2}))
            {
                int u=id2[{tmp.F,tmp.S+2}];
                ed[i].pb({u,3});
                ed[u].pb({i,4});
            }
            else ed[0].pb({i,4});
        }
        else
        {
            if(id2.count({tmp.F-2,tmp.S}))
            {
                int u=id2[{tmp.F-2,tmp.S}];
                ed[i].pb({u,1});
                ed[u].pb({i,2});
            }
            else ed[0].pb({i,2});
            if(id2.count({tmp.F+2,tmp.S}))
            {
                int u=id2[{tmp.F+2,tmp.S}];
                ed[i].pb({u,2});
                ed[u].pb({i,1});
            }
            else ed[0].pb({i,1});
        }
    }
    if(tn>0)
    {
        dfs(0);
    }
    rep(i,n) par[i]=i;
    solve();
    if(cnt<n-1) return 0;
    else
    {
        build(retu,retv,a,b);
        return 1;
    }
}
/*
for blocks:
    if (x+y)%4==0 then ud
    if (x+y)%4==2 then lr
direction:
    1: left
    2: right
    3: up
    4: down
*/
/*
signed main()
{
    MottoHayaku
    vector<int> X,Y;
    int tx,ty;
    while(cin>>tx>>ty)
    {
        X.pb(tx);
        Y.pb(ty);
    }

    ll res=construct_roads(X,Y);
    cout<<res<<"\n";
}
*/

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