Submission #1255318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255318		erering	Fountain Parks (IOI21_parks)	C++20	30 / 100	306 ms	60208 KiB

parks

#include <bits/stdc++.h>
#include "parks.h"
using namespace std;
#define pb push_back
const int MAXN=2e5+5;
int cnt[MAXN];
vector<int> adj[MAXN];
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> vec[7];
    for(int i=0;i<x.size();i++){
        exist[{x[i],y[i]}]=i+1;
        vec[x[i]].pb(y[i]);
    }
    sort(vec[2].begin(),vec[2].end());
    sort(vec[4].begin(),vec[4].end());
    sort(vec[6].begin(),vec[6].end());
    std::vector<int> u, v, a, b;
    for(int i=1;i<vec[2].size();i++){
        if(vec[2][i-1]+2==vec[2][i]){
            u.pb(exist[{2,vec[2][i-1]}]);
            v.pb(exist[{2,vec[2][i]}]);
            a.pb(1);
            b.pb(vec[2][i-1]+1);
        }
    }
    for(int i=1;i<vec[6].size();i++){
        if(vec[6][i-1]+2==vec[6][i]){
            u.pb(exist[{6,vec[6][i-1]}]);
            v.pb(exist[{6,vec[6][i]}]);
            a.pb(7);
            b.pb(vec[6][i-1]+1);
        }
    }
    cnt[0]=1;
    map<pair<int,int>,bool> taken;
    for(int i=1;i<vec[4].size();i++){
        cnt[i]=1;
        if(vec[4][i-1]+2==vec[4][i]){
            cnt[i]+=cnt[i-1];
            u.pb(exist[{4, vec[4][i - 1]}]);
            v.pb(exist[{4, vec[4][i]}]);
            b.pb(vec[4][i - 1] + 1);
            if(cnt[i]%2==0)a.pb(3);
            else a.pb(5);
            taken[{a.back(),b.back()}]=1;
        }
    }
    for(int i=0;i<vec[4].size();i++){
        int j=exist[{2,vec[4][i]}];
        if(j){
            if(!taken[{3,vec[4][i]-1}]){
                taken[{3,vec[4][i]-1}]=1;
                u.pb(j);
                v.pb(exist[{4,vec[4][i]}]);
                a.pb(3);
                b.pb(vec[4][i]-1);
            }
            else if(!taken[{3,vec[4][i]+1}]){
                taken[{3,vec[4][i]+1}]=1;
                u.pb(j);
                v.pb(exist[{4,vec[4][i]}]);
                a.pb(3);
                b.pb(vec[4][i]+1);
            }
        }
        j=exist[{6,vec[4][i]}];
        if(j){
            if(!taken[{5,vec[4][i]-1}]){
                taken[{5,vec[4][i]-1}]=1;
                u.pb(j);
                v.pb(exist[{4,vec[4][i]}]);
                a.pb(5);
                b.pb(vec[4][i]-1);
            }
            else if(!taken[{5,vec[4][i]+1}]){
                taken[{5,vec[4][i]+1}]=1;
                u.pb(j);
                v.pb(exist[{4,vec[4][i]}]);
                a.pb(5);
                b.pb(vec[4][i]+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: 15 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30