Submission #1206315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206315		simona1230	Fountain Parks (IOI21_parks)	C++20	55 / 100	1094 ms	163208 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];
map<pair<int,int>,int> use;
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));
    memset(done,0,sizeof(done));
    bench.clear();
    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];
        if(done[id])
        {
            val.pop_back();
            continue;
        }

        done[id]=1;
        a[id]=val[i].first;
        b[id]=val[i].second;
        bench[val[i]].clear();
        //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(hi==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(hi==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()==3)
            {
                if(bench[{f-1,g+1}][0]==id)bench[{f-1,g+1}]={bench[{f-1,g+1}][1],bench[{f-1,g+1}][2]};
                else if(bench[{f-1,g+1}][1]==id)bench[{f-1,g+1}]={bench[{f-1,g+1}][0],bench[{f-1,g+1}][2]};
                else bench[{f-1,g+1}]={bench[{f-1,g+1}][0],bench[{f-1,g+1}][1]};
            }
            if(bench[ {f+1,g+1}].size()==3)
            {
                if(bench[{f+1,g+1}][0]==id)bench[{f+1,g+1}]={bench[{f+1,g+1}][1],bench[{f+1,g+1}][2]};
                else if(bench[{f+1,g+1}][1]==id)bench[{f+1,g+1}]={bench[{f+1,g+1}][0],bench[{f+1,g+1}][2]};
                else bench[{f+1,g+1}]={bench[{f+1,g+1}][0],bench[{f+1,g+1}][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(hi==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(hi==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()==3)
            {
                if(bench[{f+1,g-1}][0]==id)bench[{f+1,g-1}]={bench[{f+1,g-1}][1],bench[{f+1,g-1}][2]};
                else if(bench[{f+1,g-1}][1]==id)bench[{f+1,g-1}]={bench[{f+1,g-1}][0],bench[{f+1,g-1}][2]};
                else bench[{f+1,g-1}]={bench[{f+1,g-1}][0],bench[{f+1,g-1}][1]};
            }
            if(bench[ {f+1,g+1}].size()==3)
            {
                if(bench[{f+1,g+1}][0]==id)bench[{f+1,g+1}]={bench[{f+1,g+1}][1],bench[{f+1,g+1}][2]};
                else if(bench[{f+1,g+1}][1]==id)bench[{f+1,g+1}]={bench[{f+1,g+1}][0],bench[{f+1,g+1}][2]};
                else bench[{f+1,g+1}]={bench[{f+1,g+1}][0],bench[{f+1,g+1}][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]--;

    use.clear();
    for(int i=0;i<k-1;i++)
    {
        use[{a[i],b[i]}]++;
        if(use[{a[i],b[i]}]==2)
            {
                return 0;
                /*for(int j=0;j<x.size();j++)
                    cout<<x[j]<<" "<<y[j]<<endl;

                for(int j=0;j<x.size()-1;j++)
                    cout<<a[j]<<" "<<b[j]<<endl;
                exit(0);*/
            }
    }

    build(u,v,a,b);
    //cout<<"done"<<endl;
    return 1;
}

/*pair<int,int> d[4]={{2,0},{-2,0},{0,2},{0,-2}};
map<pair<int,int>, int> t;
bool check(pair<int,int> pt)
{
    int x=pt.first,y=pt.second;
    if(!t[{x-2,y-2}]||!t[{x-2,y}]||!t[{x,y-2}])
        {
            if(!t[{x+2,y-2}]||!t[{x+2,y}]||!t[{x,y-2}])
                {
                    if(!t[{x-2,y+2}]||!t[{x-2,y}]||!t[{x,y+2}])
                        {
                            if(!t[{x+2,y+2}]||!t[{x+2,y}]||!t[{x,y+2}])
                                {
                                    return pt.first>=0&&pt.second>=0;
                                }
                        }
                }
        }
        return 0;
}
vector<int> x,y;
int nt;
void gen()
{
    t.clear();
    x={20};
    y={20};
    t[{20,20}]=1;
    nt=10;

    while(x.size()!=nt)
    {
        int r=rand()%x.size();
        pair<int,int> pt={x[r],y[r]};
        r=rand()%4;
        pt.first+=d[r].first;
        pt.second+=d[r].second;
        if(check(pt)&&!t[pt])
        {
            x.push_back(pt.first);
            y.push_back(pt.second);
            t[pt]=1;
        }
    }
}

int main()
{
    while(1)
    {
        gen();
        construct_roads(x,y);
    }
}*/

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