Submission #1034102

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034102		hotboy2703	Fountain Parks (IOI21_parks)	C++17	70 / 100	523 ms	145404 KiB

parks

#include "parks.h"

#include<bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define MASK(i) (1LL<<(i))
#define BIT(mask,i) (((mask) >> (i))&1)
struct point{
    ll x,y,id;
    point(ll x1 = 0,ll y1 = 0,ll id1 = 0):x(x1),y(y1),id(id1){}
    bool operator < (const point &p)const {
        return MP(x,y) < MP(p.x,p.y);
    }
};
namespace sub1{
    ll solve(vector <ll> x,vector <ll> y){
        for (auto z:x)if (z > 6 || z < 2)return -1;
        ll n = sz(x);
        vector <pll> all[7];
        vector <point> a(n);
        
        for (ll i = 0;i < n;i ++){
            a[i] = {x[i],y[i],i};
        }
        sort(a.begin(),a.end());
        for (ll i = 0;i < n;i ++){
            if (all[a[i].x].empty() || all[a[i].x].back().se + 2 != a[i].y)all[a[i].x].push_back(MP(a[i].y,a[i].y));
            else{
                all[a[i].x].back().se+=2;
            }
        }
        vector <int> U, V, A, B;
        auto add = [&](pll u,pll v, ll x,ll y){
            // cout<<u.fi<<' '<<u.se<<' '<<v.fi<<' '<<v.se<<endl;
            U.push_back((*lower_bound(a.begin(),a.end(),point(u.fi,u.se,0))).id);
            V.push_back((*lower_bound(a.begin(),a.end(),point(v.fi,v.se,0))).id);
            A.push_back(x);
            B.push_back(y);
        };
        for (auto x:all[2]){
            for (ll i = x.fi + 2;i <= x.se;i += 2){
                add(MP(2,i-2),MP(2,i),1,i-1);
            }
        }
        for (auto x:all[4]){
            static ll ptr2 = 0;
            static ll ptr6 = 0;
            vector <ll> sus2,sus6;
            while (ptr2 < sz(all[2]) && all[2][ptr2].se < x.fi)ptr2++;
            while (ptr2 < sz(all[2]) && all[2][ptr2].fi <= x.se){
                // cout<<all[2][ptr2].fi<<' '<<all[2][ptr2].se<<endl;
                pll tmp = all[2][ptr2];
                if (tmp.fi <= x.fi && x.fi <= tmp.se){
                    add(MP(4,x.fi),MP(2,x.fi),3,x.fi-1);
                }
                else if (tmp.fi <= x.se && x.se <= tmp.se){
                    add(MP(4,x.se),MP(2,x.se),3,x.se+1);
                }
                else{
                    sus2.push_back(tmp.fi);
                }
                ptr2++;
            }
 
            while (ptr6 < sz(all[6]) && all[6][ptr6].se < x.fi)ptr6++;
            while (ptr6 < sz(all[6]) && all[6][ptr6].fi <= x.se){
                pll tmp = all[6][ptr6];
                if (tmp.fi <= x.fi && x.fi <= tmp.se){
                    add(MP(4,x.fi),MP(6,x.fi),5,x.fi-1);
                }
                else if (tmp.fi <= x.se && x.se <= tmp.se){
                    add(MP(4,x.se),MP(6,x.se),5,x.se+1);
                }
                else{
                    sus6.push_back(tmp.fi);
                }
                ptr6++;
            }
            ptr2=0,ptr6=0;
            for (ll j = x.fi + 2;j <= x.se;j += 2){
                while(ptr2 < sz(sus2) && sus2[ptr2]<j)ptr2++; 
                while(ptr6 < sz(sus6) && sus6[ptr6]<j)ptr6++; 
                bool do2,do6;
                do2 =  (ptr2 < sz(sus2) && sus2[ptr2]==j);
                do6 =  (ptr6 < sz(sus6) && sus6[ptr6]==j);
                if (do2 && do6){
                    add(MP(4,j),MP(2,j),3,j-1);
                    add(MP(4,j),MP(6,j),5,j+1);
                    add(MP(4,j),MP(4,j-2),5,j-1);
                    add(MP(4,j),MP(4,j+2),3,j+1);
                    j+=2;
                }
                else if (do2){
                    add(MP(4,j),MP(2,j),3,j-1);
                    add(MP(4,j),MP(4,j-2),5,j-1);
                }
                else if (do6){
                    add(MP(4,j),MP(6,j),5,j-1);
                    add(MP(4,j),MP(4,j-2),3,j-1);
                }
                else add(MP(4,j),MP(4,j-2),3,j-1);
            }
        } 
        for (auto x:all[6]){
            for (ll i = x.fi + 2;i <= x.se;i += 2){
                add(MP(6,i-2),MP(6,i),7,i-1);
            }
        }
        {
            vector <vector <ll > > g(n);
            for (ll i = 0;i < sz(U);i ++){
                g[U[i]].push_back(V[i]);
                g[V[i]].push_back(U[i]);
            }
            vector <bool> in(n);
            queue <ll> q;
            q.push(0);
            in[0] = 1;
            while (!q.empty()){
                ll u = q.front();
                q.pop();
                for (auto v:g[u]){
                    if (!in[v]){
                        in[v] = 1;
                        q.push(v);
                    }
                }
            }
            for (ll i = 0;i < n;i ++)if (!in[i])return 0;
            build(U, V, A, B);
            return 1;
        }
    }
}
const ll MAXN = 2e5+100;
ll dsu[MAXN];
ll f(ll x){
    if (dsu[x] < 0)return x;
    return (dsu[x] = f(dsu[x]));
}
bool join(ll x,ll y){
    x = f(x),y = f(y);
    if (x==y)return 0;
    dsu[x] += dsu[y];
    dsu[y] = x;
    return 1;
}
struct road{
    pll a,b;
    ll id;
};
namespace scc{
    vector <pair <pll,bool> > query;
    void add_or(ll x,ll y,bool neg = 0){
        // cout<<x<<' '<<y<<'\n';
        query.push_back(MP(MP(x,y),neg));
    }
    vector <vector <ll> > g1,g2;
    vector <bool> in;
    void add(ll x,ll y){
        g1[x].push_back(y);
        g2[y].push_back(x);
    }
    void dfs(vector <vector <ll> > &adj,ll u,vector <ll> &order){
        in[u] = 1;
        for (auto v:adj[u]){
            if (!in[v]){
                dfs(adj,v,order);
            }
        }
        order.push_back(u);
    }
    bool solve(vector <bool> &res){
        ll n=sz(res)*2;
        g1.resize(n);
        g2.resize(n);
        for (auto x:query){
            if (x.se){ 
                add(x.fi.fi<<1,x.fi.se<<1|1);
                add(x.fi.se<<1,x.fi.fi<<1|1);
            }
            else{
                add(x.fi.fi<<1|1,x.fi.se<<1);
                add(x.fi.se<<1|1,x.fi.fi<<1);
            }
        }
        vector <ll> order;
        in = vector <bool> (n,0);
        vector <ll> c(n);
        for (ll i = 0;i < n;i ++){
            if (!in[i]){
                dfs(g1,i,order);
            }
        }
        in = vector <bool> (n,0);
        reverse(order.begin(),order.end());
        ll ptr = 0;
        for (auto x:order){
            if (!in[x]) {
                vector <ll> comp;
                dfs(g2,x,comp);
                for (auto x:comp)c[x] = ptr;
                ptr++;
            }
        }
        for (ll i = 0;i < sz(res);i ++){
            if (c[i<<1]==c[i<<1|1])return 0;
            res[i] = c[i<<1] > c[i<<1|1];
            // cout<<res[i]<<' ';
        }
        // cout<<'\n';
        return 1;
    }
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    ll tmp = sub1::solve(x,y);
    if (tmp != -1)return tmp;
    ll n = sz(x);
    vector <point> a(n);
    
    for (ll i = 0;i < n;i ++){
        dsu[i] = -1;
        a[i] = {x[i],y[i],i};
    }
    sort(a.begin(),a.end());
    auto id = [&](pll x){
        auto tmp = lower_bound(a.begin(),a.end(),point(x.fi,x.se,0));
        if (tmp != a.end() && (*tmp).x==x.fi&&(*tmp).y==x.se)return (*tmp).id;
        else return -1;
    };
    vector <road> all;
    for (ll i = 0;i < n;i ++){
        if (id(MP(a[i].x,a[i].y-2)) != -1) {
            if (join(id(MP(a[i].x,a[i].y-2)),a[i].id)) {
                all.push_back({MP(id(MP(a[i].x,a[i].y-2)),a[i].id),MP(a[i].x-1,a[i].y-1),sz(all)});
                all.push_back({MP(id(MP(a[i].x,a[i].y-2)),a[i].id),MP(a[i].x+1,a[i].y-1),sz(all)});
                scc::add_or(sz(all)-1,sz(all)-2);
                scc::add_or(sz(all)-1,sz(all)-2,1);
            }
        }
        if ((id(MP(a[i].x-2,a[i].y)) != -1)) {
            if (join(id(MP(a[i].x-2,a[i].y)),a[i].id)) {
                all.push_back({MP(id(MP(a[i].x-2,a[i].y)),a[i].id),MP(a[i].x-1,a[i].y+1),sz(all)});
                all.push_back({MP(id(MP(a[i].x-2,a[i].y)),a[i].id),MP(a[i].x-1,a[i].y-1),sz(all)});
                scc::add_or(sz(all)-1,sz(all)-2);
                scc::add_or(sz(all)-1,sz(all)-2,1);
            }
        }
    }
    if (dsu[f(0)] != -n)return 0;
    sort(all.begin(),all.end(),[](road a1,road a2){return a1.b < a2.b;});
    for (ll i = 0;i + 1 < sz(all);i ++){
        if (all[i].b == all[i+1].b){
            // cout<<all[i].a.fi<<' '<<all[i].a.se<<' '<<all[i+1].a.fi<<' '<<all[i+1].a.se<<' '<<all[i].id<<' '<<all[i+1].id<<endl;
            scc::add_or(all[i].id,all[i+1].id,1);
        }
    }
    vector <bool> res(sz(all));
    if (!scc::solve(res))return 0;

    {
        vector <ll> U,V,A,B;
        for (ll i = 0;i < sz(all);i ++){
            if (res[all[i].id]){
                U.push_back(all[i].a.fi);
                V.push_back(all[i].a.se);
                A.push_back(all[i].b.fi);
                B.push_back(all[i].b.se);
            }
        }
        build(U, V, A, B);
        return 1;
    }
}

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