Submission #1204850

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204850		simona1230	Fountain Parks (IOI21_parks)	C++20	5 / 100	846 ms	150664 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=2*1e5+5;
pair<int,int> p[maxn];
map<pair<int,int>, int> mp,e;
map<pair<int,int>, vector<int> > bench;
int k,used[maxn];
int in;

vector<int> v,u,a,b;

void dfs(int i,int l)
{
    //cout<<i<<endl;
    in++;
    if(i!=1)
    {
        if(p[i].first==p[l].first)
        {
            int heh=min(p[i].second,p[l].second)+1;
            bench[ {p[i].first-1,heh}].push_back(v.size());
            bench[ {p[i].first+1,heh}].push_back(v.size());
        }
        else
        {
            int heh=min(p[i].first,p[l].first)+1;
            bench[ {heh,p[i].second-1}].push_back(v.size());
            bench[ {heh,p[i].second+1}].push_back(v.size());
        }

        v.push_back(l);
        u.push_back(i);
        e[ {i,l}]=e[ {l,i}]=1;
    }

    used[i]=1;
    pair<int,int> c;
    c=p[i];
    c.first+=2;
    if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
    c=p[i];
    c.first-=2;
    if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
    c=p[i];
    c.second+=2;
    if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
    c=p[i];
    c.second-=2;
    if(mp[c]&&!used[mp[c]])dfs(mp[c],i);
}

int done[maxn];
int construct_roads(std::vector<int> x, std::vector<int> y)
{
    mp.clear();
    e.clear();
    v.clear();
    u.clear();
    a.clear();
    b.clear();
    memset(used,0,sizeof(used));
    in=0;

    k=x.size();
    for(int i=0; i<k; i++)
    {
        p[i+1]= {x[i],y[i]};
        mp[p[i+1]]=i+1;
    }

    dfs(1,0);
    if(in!=k)return 0;

    vector<pair<int,int> > val;
    for(int i=0; i<k-1; i++)
    {
        pair<int,int> p1=p[v[i]],p2=p[u[i]];
        if(p1.first==p2.first)
        {
            int f=p1.first;
            int g=min(p1.second,p2.second);
            if(bench[ {f-1,g+1}].size()==1)val.push_back({f-1,g+1});
            if(bench[ {f+1,g+1}].size()==1)val.push_back({f+1,g+1});
        }
        else
        {
            int f=min(p1.first,p2.first);
            int g=p1.second;
            if(bench[ {f+1,g-1}].size()==1)val.push_back({f+1,g-1});
            if(bench[ {f+1,g+1}].size()==1)val.push_back({f+1,g+1});
        }
    }
    /*cout<<"out"<<endl;
    for(int i=0;i<val.size();i++)
        cout<<val[i].first<<" "<<val[i].second<<endl;*/

    a.resize(x.size()-1);
    b.resize(x.size()-1);
    while(val.size())
    {
        int i=val.size()-1;
        int id=bench[val[i]][0];

        done[id]=1;
        a[id]=val[i].first;
        b[id]=val[i].second;
        //cout<<id<<endl;
        //cout<<val[i].first<<" "<<val[i].second<<endl;
        val.pop_back();

        pair<int,int> p1=p[v[id]],p2=p[u[id]];
        if(p1.first==p2.first)
        {
            int f=p1.first;
            int g=min(p1.second,p2.second);
            if(bench[ {f-1,g+1}].size()==2)
            {
                int hi=bench[{f-1,g+1}][0];
                if(p[hi].first==a[id]&&p[hi].second==b[id])bench[{f-1,g+1}]={bench[{f-1,g+1}][1]};
                else bench[{f-1,g+1}]={bench[{f-1,g+1}][0]};
                val.push_back({f-1,g+1});
            }
            if(bench[ {f+1,g+1}].size()==2)
            {
                int hi=bench[{f+1,g+1}][0];
                if(p[hi].first==a[id]&&p[hi].second==b[id])bench[{f+1,g+1}]={bench[{f+1,g+1}][1]};
                else bench[{f+1,g+1}]={bench[{f+1,g+1}][0]};
                val.push_back({f+1,g+1});
            }
        }
        else
        {
            int f=min(p1.first,p2.first);
            int g=p1.second;
            if(bench[ {f+1,g-1}].size()==2)
            {
                int hi=bench[{f+1,g-1}][0];
                if(p[hi].first==a[id]&&p[hi].second==b[id])bench[{f+1,g-1}]={bench[{f+1,g-1}][1]};
                else bench[{f+1,g-1}]={bench[{f+1,g-1}][0]};
                val.push_back({f+1,g-1});
            }
            if(bench[ {f+1,g+1}].size()==2)
            {
                int hi=bench[{f+1,g+1}][0];
                if(p[hi].first==a[id]&&p[hi].second==b[id])bench[{f+1,g+1}]={bench[{f+1,g+1}][1]};
                else bench[{f+1,g+1}]={bench[{f+1,g+1}][0]};
                val.push_back({f+1,g+1});
            }
        }
    }

    for(int i=0; i<k-1; i++)
    {
        if(done[i])continue;
        pair<int,int> p1=p[v[i]],p2=p[u[i]];
        if(p1.first==p2.first)
        {
            int f=p1.first;
            int g=min(p1.second,p2.second);
            b[i]=g+1;
            if(e[ {mp[{f,g}],mp[{f-2,g}]}]||e[ {mp[{f,g}],mp[{f+2,g}]}])
                a[i]=f+1;
            else a[i]=f-1;
        }
        else
        {
            int f=min(p1.first,p2.first);
            int g=p1.second;
            a[i]=f+1;
            if(e[ {mp[{f,g}],mp[{f,g-2}]}]||e[ {mp[{f,g}],mp[{f,g+2}]}])
                b[i]=g-1;
            else b[i]=g+1;
        }
    }

    for(int i=0; i<k-1; i++)
        v[i]--,u[i]--;

    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