Submission #1204815

#	Time	Username	Problem	Language	Result	Execution time	Memory
1204815		simona1230	Fountain Parks (IOI21_parks)	C++20	5 / 100	3600 ms	127904 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,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)
    {
        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 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;

    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);
            b.push_back(g+1);
            if(e[{mp[{f,g}],mp[{f-2,g}]}]||e[{mp[{f,g}],mp[{f+2,g}]}])
                a.push_back(f+1);
            else a.push_back(f-1);
        }
        else
        {
            int f=min(p1.first,p2.first);
            int g=p1.second;
            a.push_back(f+1);
            if(e[{mp[{f,g}],mp[{f,g-2}]}]||e[{mp[{f,g}],mp[{f,g+2}]}])
                b.push_back(g-1);
            else b.push_back(g+1);
        }
        if(bench[{a[i],b[i]}])while(1);
        bench[{a[i],b[i]}]=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