Submission #441374

#	Time	Username	Problem	Language	Result	Execution time	Memory
441374		daniel920712	Fountain Parks (IOI21_parks)	C++17	15 / 100	538 ms	31688 KiB

parks

#include "parks.h"
#include <map>
#include <utility>
using namespace std;
map < pair < int , int > , int > all;
vector < int > u,v,a,b;
int Father[200005];
int Find(int here)
{
    if(Father[here]==here) return here;
    Father[here]=Find(Father[here]);
    return Father[here];
}
int construct_roads(vector < int > x, vector < int > y)
{
    int N=x.size(),i,t,aa,bb,ok=1;
    for(i=0;i<N;i++)
    {
        all[make_pair(x[i],y[i])]=i;
        Father[i]=i;
    }
    for(i=0;i<N;i++)
    {
        if(all.find(make_pair(x[i],y[i]+2))!=all.end())
        {
            t=all[make_pair(x[i],y[i]+2)];
            u.push_back(i);
            v.push_back(t);
            if(x[i]==2) a.push_back(1);
            else a.push_back(5);
            b.push_back(y[i]+1);
            aa=Find(i);
            bb=Find(t);
            if(aa!=bb) Father[aa]=bb;
        }
        if(all.find(make_pair(x[i]+2,y[i]))!=all.end())
        {
            t=all[make_pair(x[i]+2,y[i])];
            u.push_back(i);
            v.push_back(t);
            a.push_back(3);
            b.push_back(y[i]+1);
            aa=Find(i);
            bb=Find(t);
            if(aa!=bb) Father[aa]=bb;
        }

    }
    t=Find(0);
    for(i=0;i<N;i++)
    {
        if(t!=Find(i)) ok=0;
    }
    if(ok) build(u,v,a,b);
    return ok;
}

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