Submission #1255327

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255327		erering	Fountain Parks (IOI21_parks)	C++20	15 / 100	499 ms	76820 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],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;
    vector<int> uniq;
    set<int> st;
    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]);
    }
    for(auto i:st)uniq.pb(i);
    sort(uniq.begin(),uniq.end());
    map<pair<int,int>,bool> taken;
    for(int id=0;id<uniq.size();id++){
        int i=uniq[id];
        sort(vec[i].begin(),vec[i].end());
        int cnt=0;
        for(int j=1;j<vec[i].size();j++){
            if(vec[i][j-1]+2==vec[i][j]){
                cnt++;
                u.pb(exist[{vec[i][j - 1],i}]);
                v.pb(exist[{vec[i][j],i}]);
                a.pb(vec[i][j]-1);
                if(cnt%2==1)b.pb(i-1);
                else b.pb(i+1);
                taken[{a.back(),b.back()}]=1;
            }
            else cnt=0;
        }
        if(id>0){
            for(int j=0;j<vec[i].size();j++){
                int k=exist[{vec[i][j],i-2}];
                if(k){
                    u.pb(k);
                    v.pb(exist[{vec[i][j],i}]);
                    b.pb(i-1);
                    if(!taken[{vec[i][j]-1,i-1}]){
                        taken[{vec[i][j]-1,i-1}]=1;
                        a.pb(vec[i][j]-1);
                    }
                    else if(!taken[{vec[i][j]+1,i-1}]){
                        taken[{vec[i][j]+1,i-1}]=1;
                        a.pb(vec[i][j]+1);
                    }
                    else exit(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: 10 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30