Submission #1204135

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204135		simona1230	Fountain Parks (IOI21_parks)	C++20	5 / 100	885 ms	101824 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=5*1e5+5;

struct fount
{
    int x,y,i;
    fount() {}
    fount(int _x,int _y,int _i)
    {
        x=_x;
        y=_y;
        i=_i;
    }
};

bool cmp(fount f1,fount f2)
{
    return f1.y<f2.y;
}

int c;
fount p[maxn];
map<pair<int,int>,int> mp,mp1;
vector<int> u,v,a,b;
int used[maxn],in;
void dfs(int i,int pr)
{
    if(pr!=-1)
    {
        v.push_back(i-1);
        u.push_back(pr-1);
        mp1[ {i-1,pr-1}]=1;
        mp1[ {pr-1,i-1}]=1;
    }

    in++;
    int cnt=0;
    used[i]=1;

    pair<int,int> h= {p[i].x,p[i].y};
    h.first+=2;

    if(mp[h]&&!used[mp[h]])
    {
        cnt++;
        dfs(mp[h],i);
    }

    h.first-=4;
    if(mp[h]&&!used[mp[h]])
    {
        cnt++;
        dfs(mp[h],i);
    }
    h.first+=2;

    h.second+=2;
    if(mp[h]&&!used[mp[h]])
    {
        cnt++;
        dfs(mp[h],i);
    }
    h.second-=4;
    if(mp[h]&&!used[mp[h]])
    {
        cnt++;
        dfs(mp[h],i);
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y)
{
    c=x.size();
    for(int i=0; i<x.size(); i++)
    {
        p[i+1]= {x[i],y[i],i};
        mp[ {x[i],y[i]}]=i+1;
    }

    dfs(1,-1);
    if(in!=x.size())return 0;

    for(int i=0; i<x.size()-1; i++)
    {
        if(p[v[i]+1].x==p[u[i]+1].x)
        {
            int x=p[v[i]+1].x;
            int y=min(p[v[i]+1].y,p[u[i]+1].y);

            if(mp[ {x-2,y}]&&mp1[ {mp[{x,y}],mp[{x-2,y}]}]||mp[ {x+2,y}]&&mp1[ {mp[{x,y}],mp[{x+2,y}]}])
            {
                a.push_back(x-1);
                b.push_back(y+1);
            }
            else
            {
                a.push_back(x+1);
                b.push_back(y+1);
            }
        }
        else
        {
            int x=min(p[v[i]+1].x,p[u[i]+1].x);
            int y=p[v[i]+1].y;

            if(mp[ {x,y-2}]&&mp1[ {mp[{x,y}],mp[{x,y-2}]}]||mp[ {x,y+2}]&&mp1[ {mp[{x,y}],mp[{x,y+2}]}])
            {
                a.push_back(x+1);
                b.push_back(y+1);
            }
            else
            {
                a.push_back(x+1);
                b.push_back(y-1);
            }
        }
    }

    build(v,u,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