제출 #602388

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
602388		rrrr10000	분수 공원 (IOI21_parks)	C++17	30 / 100	641 ms	49908 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef vector<P> vp;
typedef vector<vp> vvp;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define fi first
#define se second
#define pb emplace_back
#define all(a) a.begin(),a.end()
template<class T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<endl;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
vi dx={2,0,-2,0},dy={0,2,0,-2};
ll mx=200005;
int construct_roads(std::vector<int> X, std::vector<int> Y) {
    if (X.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    ll n=X.size();
    map<P,ll> mp;
    rep(i,n)mp[P(X[i],Y[i])]=i;
    vp edge;
    rep(i,n)rep(j,2){
        ll nx=X[i]+dx[j],ny=Y[i]+dy[j];
        if(mp.count(P(nx,ny)))edge.pb(i,mp[P(nx,ny)]);
    }
    {
        vvi g(n);
        for(auto x:edge){
            g[x.fi].pb(x.se);
            g[x.se].pb(x.fi);
        }
        queue<ll> que;
        vb done(n,false);
        done[0]=true;
        que.push(0);
        while(!que.empty()){
            ll t=que.front();que.pop();
            for(ll x:g[t])if(!done[x]){
                done[x]=true;que.push(x);
            }
        }
        rep(i,n)if(!done[i])return 0;
    }
    vvp al(mx);
    rep(i,n)al[Y[i]].pb(X[i],i);
    rep(i,mx)sort(all(al[i]));
    vector<int> u, v, a, b;
    auto add=[&](ll i,ll j,ll t){
        u.pb(i);v.pb(j);
        if(t==0||t==1){
            assert(Y[i]==Y[j]);
            a.pb((X[i]+X[j])/2);
            if(t==0)b.pb(Y[i]-1);
            else b.pb(Y[i]+1);
        }
        else{
            assert(X[i]==X[j]);
            b.pb((Y[i]+Y[j])/2);
            if(t==2)a.pb(X[i]-1);
            else a.pb(X[i]+1);
        }
    };
    bool small=true;
    rep(i,n)if(X[i]>6)small=false;
    if(small){
        vb tmp(2,false);
        rep(i,mx)if(al[i].size()){
            vb ntmp(2,false);
            if(!al[i-2].size()){
                rep(j,al[i].size()-1)if(al[i][j+1].fi-al[i][j].fi==2)add(al[i][j].se,al[i][j+1].se,0);
            }
            else{
                if(al[i].back().fi==6&&al[i-2].back().fi==6)add(al[i].back().se,al[i-2].back().se,3);
                if(al[i][0].fi==2&&al[i-2][0].fi==2)add(al[i][0].se,al[i-2][0].se,2);
                if(al[i][0].fi==4&&al[i-2].back().fi==4){
                    add(al[i][0].se,al[i-2].back().se,3);
                    if(al[i].size()>1){
                        add(al[i][0].se,al[i][1].se,1);
                        ntmp[1]=true;
                    }
                }
                else if(al[i].back().fi==4&&al[i-2][0].fi==4){
                    add(al[i].back().se,al[i-2][0].se,2);
                    if(al[i].size()>1){
                        add(al[i][0].se,al[i][1].se,1);
                        ntmp[0]=true;
                    }
                }
                else if(al[i-2].size()==3&&al[i].size()==1&&al[i][0].fi==4){
                    if(tmp[1])add(al[i-2][1].se,al[i][0].se,2);
                    else add(al[i-2][1].se,al[i][0].se,3);
                }
                else if(al[i-2].size()==1&&al[i-2][0].fi==4&&al[i].size()==3){
                    add(al[i-2][0].se,al[i][1].se,3);
                    add(al[i][0].se,al[i][1].se,0);
                    add(al[i][1].se,al[i][2].se,1);
                    ntmp[1]=true;
                }
                else{
                    rep(j,al[i].size()-1)if(al[i][j+1].fi-al[i][j].fi==2){
                        ll t=al[i][j].fi/2-1;
                        if(tmp[t]){
                            ntmp[t]=true;add(al[i][j].se,al[i][j+1].se,1);
                        }
                        else add(al[i][j].se,al[i][j+1].se,0);
                    }
                }
            }
            tmp=ntmp;
        }
        build(u, v, a, b);
        return 1;
    }
    for(auto x:edge){
        u.pb(x.fi);v.pb(x.se);
        P p((X[x.fi]+X[x.se])/2,(Y[x.fi]+Y[x.se])/2);
        if(X[x.fi]==X[x.se]){
            p.fi++;
            if((p.fi+p.se)%4==2)p.fi-=2;
        }
        else{
            p.se++;
            if((p.fi+p.se)%4==0)p.se-=2;
        }
        a.pb(p.fi);b.pb(p.se);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:30:15: warning: control reaches end of non-void function [-Wreturn-type]
   30 |     map<P,ll> mp;
      |               ^~

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