Submission #1206356

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206356		simona1230	Fountain Parks (IOI21_parks)	C++20	30 / 100	1233 ms	127812 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;
int l[maxn],sz[maxn];
int done[maxn];
int cnt[maxn];
map<pair<int,int>,int> use;
void connect(int i,int l)
{
    in++;
    cnt[i]++;
    cnt[l]++;
    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;
}

int fl(int x)
{
    if(x==l[x])return x;
    return l[x]=fl(l[x]);
}

void unite(int i,int j)
{
    int li=fl(i);
    int lj=fl(j);
    if(li!=lj)
    {
        connect(i,j);
        if(sz[li]>sz[lj])swap(li,lj);
        l[li]=lj;
        sz[lj]+=sz[li];
    }
}

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++)
    {
        l[i+1]=i+1;
        sz[i+1]=1;

        p[i+1]= {x[i],y[i]};
        mp[p[i+1]]=i+1;
    }


    for(int i=1;i<=k;i++)
    {
        int j=mp[{p[i].first,p[i].second+2}];
        if(j)unite(i,j);
    }

    for(int i=1;i<=k;i++)
    {
        if(cnt[i]>1)continue;
        int j=mp[{p[i].first+2,p[i].second}];
        if(j)unite(i,j);
        j=mp[{p[i].first-2,p[i].second}];
        if(j)unite(i,j);
    }

    if(in!=k-1)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]];
        //cout<<p1.first<<" "<<p1.second<<" "<<p2.first<<" "<<p2.second<<endl;
        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}]}]&&e[ {mp[{f,g}],mp[{f,g-2}]}])
                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}]}]&&e[ {mp[{f,g}],mp[{f-2,g}]}])
                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 1;
        }
    }

    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;
    return x>=0&&y>=0;
}
vector<int> x,y;
int nt;
void gen()
{
    t.clear();
    x= {20};
    y= {20};
    t[ {20,20}]=1;
    nt=8;

    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: 15 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30