Submission #1196402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196402		Amr	Fountain Parks (IOI21_parks)	C++20	0 / 100	4 ms	7492 KiB

parks

/*#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
const int N = 3e5+2;
vector<ll> points[N];
ll n;
int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    n = x.sz;
    for(int i = 0; i < n; i++)
    {
        points[i] = {x[i],y[i],i};
    }
    sort(points,points+n);
    vector<int> v1, v2, v3, v4;
    for(int i = 1; i < n; i++)
    {
        if(points[i-1][1]+2!=points[i][1]) return 0;
        v1.push_back(points[i-1][2]);
        v2.push_back(points[i][2]);
        v3.push_back(1);
        v4.push_back(points[i][1]-1);
    }
    build(v1,v2,v3,v4);
    return 1;
}*/

#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define S second
#define F first
const int N = 3e5+2;
vector<ll> points[N];
ll n;

vector<int> v1,v2,v3,v4;
ll dx[] = {-2,0,2,0};
ll dy[] = {0,-2,0,2};
ll p[N];
pair<ll,ll> pos[N];
ll a[5][200005];

ll get(ll x)
{
    if(x==p[x]) return x;
    return p[x] = get(p[x]);
}
bool valid(ll x, ll y)
{
    if(x==0||x==6) return 0;
    if(y==0) return 0;
    return 1;
}
void merg(ll x, ll y, ll k)
{
    x = get(x); y = get(y);
    if(x==y) return;
    p[x] = y;
    // 0 left , 1 down , 2 right, 3 up
    v1.push_back(x-1);
    v2.push_back(y-1);
    ll midx, midy;
    if(k==0||k==2)
    {
         midy = pos[x].S-1;
         midx = 3;
    }
    else // down
    {
        if(pos[x].F==2)
        {
             midy = (pos[x].S+pos[y].S)/2;
             midx = 1;
        }
        else
        {
            midy = (pos[x].S+pos[y].S)/2;
            midx = 5;
        }
    }
    v3.push_back(midx);
    v4.push_back(midy);
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    n = x.sz;
   // 1,2
    for(int i = 0; i < n; i++)
    {
        a[x[i]][y[i]] = i+1;
        pos[i+1] = {x[i],y[i]};
        p[i+1] = i+1;
        for(int k = 0; k < 4; k++)
        {
            ll newx = x[i] + dx[k] , newy = y[i] + dy[k];
            if(valid(newx,newy)&&a[newx][newy]!=0)
            {
                merg(i+1,a[newx][newy],k);
            }
        }
    }
    ll cnt = 0;
    for(int i = 1; i <= n; i++) if(p[i]==i) cnt++;
    if(cnt>1) return 0;
    build(v1,v2,v3,v4);

    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