Submission #436729

#	Time	Username	Problem	Language	Result	Execution time	Memory
436729		David_M	Fountain Parks (IOI21_parks)	C++17	0 / 100	1125 ms	1048580 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define F first
#define S second
 
map <pair<int, int>, int> m;
int ff[800010], f[800010], n, L[800010], D[800010], e, aa;
vector<int> A1, A2, A3, A4, v[800010], xx, yy;
pair<int, int> t[800010], W[800010];
 
void Ans(int x, int y){
    if(f[x] || f[y])return;
    f[x]=f[y]=1;
    if(x>y)swap(x, y);
    if(x<n)A1.pb( x ), A2.pb( L[x] );
    else   A1.pb(x-n), A2.pb(D[x-n]);
    A3.pb(t[y].F),
    A4.pb(t[y].S);
}
 
void dfs(int x){
    ff[x]=1;
    for(auto y:v[x]){
        if(ff[y])continue;
        Ans(x,y);
        dfs(y);
    }
}
 
void DFS(int x, int y){
    aa++;
    if(m[{x-2, y}])DFS(x-2, y);
    if(m[{x+2, y}])DFS(x+2, y);
    if(m[{x, y-2}])DFS(x, y-2);
    if(m[{x, y+2}])DFS(x, y+2);
}
 
int construct_roads(vector<int> x, vector<int> y) {
 
    for (auto i:x)xx.pb(i);
    for (auto i:y)yy.pb(i);
 
    n=x.size();
    int o=2*n;
 
    for (int i=1; i<=n; i++)m[{x[i-1], y[i-1]}]=i;
    DFS(x[0], y[0]);
    if(aa<n)return 0;
    for (int i=1; i<=n; i++){
        int X=x[i-1], Y=y[i-1];
        if(m[{X, Y-2}]){
            W[i]={i, m[{X, Y-2}]};
            L[i]=m[{X, Y-2}];
            if(!m[{X-1, Y-1}])t[++o]={X-1, Y-1}, m[{X-1, Y-1}]=o;
            e=m[{X-1, Y-1}];
            v[e].pb(i);
            v[i].pb(e);
            if(!m[{X+1, Y-1}])t[++o]={X+1, Y-1}, m[{X+1, Y-1}]=o;
            e=m[{X+1, Y-1}];
            v[e].pb(i);
            v[i].pb(e);
        }
        if(m[{X-2, Y}]){
            W[i+n]={i, m[{X-2, Y}]};
            D[i]=m[{X-2, Y}];
            if(!m[{X-1, Y-1}])t[++o]={X-1, Y-1}, m[{X-1, Y-1}]=o;
            e=m[{X-1, Y-1}];
            v[e].pb(i+n);
            v[i+n].pb(e);
            if(!m[{X-1, Y+1}])t[++o]={X-1, Y+1}, m[{X-1, Y+1}]=o;
            e=m[{X-1, Y+1}];
            v[e].pb(i+n);
            v[i+n].pb(e);
        }
    }
 
    for (int i=1; i<=2*n; i++){
        if(v[i].size()&&!ff[i])dfs(i);
    }
    build(A1, A2, A3, A4);
    return 1;
}

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