Submission #1255356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255356		erering	Fountain Parks (IOI21_parks)	C++20	5 / 100	1712 ms	122772 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
#define pb push_back
const int MAXN=2e5+5;
vector<int> adj[MAXN],vec[MAXN],all[MAXN],u,v,a,b;
bool vis[MAXN];
void dfs(int node){
    if(vis[node])return;
    vis[node]=1;
    for(auto i:adj[node])dfs(i);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    map<pair<int,int>,int> exist;
    set<int> st,st2;
    for(int i=0;i<x.size();i++){
        exist[{x[i],y[i]}]=i+1;
        vec[y[i]].pb(x[i]);
        st.insert(y[i]);
        st2.insert(x[i]);
        all[x[i]].pb(y[i]);
    }
    for(auto i:st2)sort(all[i].begin(),all[i].end());
    map<pair<int,int>,pair<int,int>> start,belong;
    for(auto i:st){
        int curx,cury;
        sort(vec[i].begin(),vec[i].end());
        for(auto j:vec[i]){
            int X=j,Y=i;
            int k=exist[{X-2,Y}];
            if(k){
                if(start[{curx,cury}].second==-1)start[{curx,cury}].second=0;
                start[{curx,cury}].second^=1;
            }
            else{
                start[{X,Y}]={1,-1}; //1 means up 0 means down
                curx=X; cury=Y;
            }
            belong[{X,Y}]={curx,cury};
        }
    }
    for(auto i:st2){
        for(auto j:all[i]){
            int X=i,Y=j;
            int k=exist[{X,Y-2}];
            if(start[{X,Y}].second==-1 || start[{X,Y-2}].second==-1)continue;
            if(k){
                u.pb(k);
                v.pb(exist[{X,Y}]);
                b.pb(Y-1);
                if(belong[{X,Y}]==make_pair(X,Y)){
                    if(!start[belong[{X,Y}]].second && start[{X,Y-2}].first){
                        start[{X,Y}].first^=1;
                        start[{X,Y}].second^=1;
                    }
                    if(start[belong[{X,Y}]].first)a.pb(X+1);
                    else a.pb(X-1);
                }
                else{
                    if(!start[belong[{X,Y}]].second && start[{X,Y-2}].first){
                        start[{X,Y-2}].first^=1;
                        start[{X,Y-2}].second^=1;
                    }
                    if(start[belong[{X,Y}]].first)a.pb(X-1);
                    else a.pb(X+1);
                }
            }
        }
    }
    for(int i=0;i<x.size();i++){
        int X=x[i],Y=y[i];
        if(belong[{X,Y}]==make_pair(X,Y)){
            int cur=start[{X,Y}].first;
            for(int j=X+2;true;j+=2){
                if(!exist[{j,Y}])break;
                u.pb({exist[{j,Y}]});
                v.pb({exist[{j-2,Y}]});
                a.pb(j-1);
                if(cur)b.pb(Y+1);
                else b.pb(Y-1);
                cur^=1;
            }
        }
    }
    map<pair<int,int>,bool> taken;
    for(int i=0;i<a.size();i++)taken[{a[i],b[i]}]=1;
    for(int i=0;i<x.size();i++){
        int X=x[i],Y=y[i];
        if(make_pair(X,Y)!=belong[{X,Y}] || start[{X,Y}].second!=-1)continue;
        int k=exist[{X,Y-2}];
        if(k){
            u.pb(k);
            v.pb(i+1);
            b.pb(Y-1);
            if(!taken[{X-1,Y-1}]){
                taken[{X-1,Y-1}]=1;
                a.pb(X-1);
            }
            else if(!taken[{X+1,Y-1}]){
                taken[{X+1,Y-1}]=1;
                a.pb(X+1);
            }
        }
        if(start[{X,Y+2}].second==-1)continue;
        k=exist[{X,Y+2}];
        if(k){
            u.pb(k);
            v.pb(i+1);
            b.pb(Y+1);
            if(!taken[{X+1,Y+1}]){
                taken[{X+1,Y+1}]=1;
                a.pb(X+1);
            }
            else if(!taken[{X-1,Y+1}]){
                taken[{X-1,Y+1}]=1;
                a.pb(X-1);
            }
        }
    }
    for(int i=0;i<v.size();i++){
        u[i]--;
        v[i]--;
        adj[u[i]].pb(v[i]); adj[v[i]].pb(u[i]);
    }
    dfs(0);
    for(int i=0;i<x.size();i++){
        if(!vis[i]){
            return 0;
        }
    }
    build(u, v, a, b);
    return 1;
}

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