Submission #1270937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270937		nerrrmin	Fountain Parks (IOI21_parks)	C++20	0 / 100	2 ms	324 KiB

parks

#include "parks.h"
#define pb push_back
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
int nn;
vector < int > p[maxn];
vector < pair < int, int > > h[maxn];
int used[maxn], seen;
void dfs(int beg, int from)
{

    used[beg] = 1;
    seen ++;
    for(auto nb: p[beg])
    {
        if(used[nb])continue;
        dfs(nb, beg);
    }
}
int construct_roads(std::vector<int> x, std::vector<int> y)
{

    if (x.size() == 1)
    {
        build({}, {}, {}, {});
        return 1;
    }
    nn = x.size();
    vector < pair < int, int > > g[5];
    for (int i = 0; i < nn; ++ i)
    {
        if(x[i] == 2)g[2].pb(make_pair(y[i], i));
        if(x[i] == 4)g[4].pb(make_pair(y[i], i));

            h[y[i]].pb(make_pair(x[i], i));

    }

    sort(g[2].begin(), g[2].end());
    sort(g[4].begin(), g[4].end());
    std::vector<int> u, v, a, b;
    for (int i = 0 ; i < g[2].size(); ++ i)
    {
        if(i == 0)continue;
        if(g[2][i].first - g[2][i-1].first != 2)continue;
        int index1 = g[2][i].second;
        int index2 = g[2][i-1].second;
        p[index1].pb(index2);
        p[index2].pb(index1);
        u.pb(index1);
        v.pb(index2);
        a.pb(0);
        b.pb(g[2][i].first - 1);
    }
    for (int i = 0 ; i < g[4].size(); ++ i)
    {
        if(i == 0)continue;
        if(g[4][i].first - g[4][i-1].first != 2)continue;
        int index1 = g[4][i].second;
        int index2 = g[4][i-1].second;
        p[index1].pb(index2);
        p[index2].pb(index1);
        u.pb(index1);
        v.pb(index2);
        a.pb(5);
        b.pb(g[4][i].first - 1);
    }
    for (int i = 1; i <= 2e5; ++ i)
    {
        if(h[i].size() == 2)
        {
            int index1 = h[i][0].second;
            int index2 = h[i][1].second;

            p[index1].pb(index2);
            p[index2].pb(index1);
            u.pb(index1);
            v.pb(index2);
            a.pb(3);
            b.pb(i-1);
        }
    }

    dfs(0, -1);
    if(seen != nn)return 0;
    build(u, v, a, b);
    return 1;
}

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