Submission #819897

#	Time	Username	Problem	Language	Result	Execution time	Memory
819897		HorizonWest	Fountain Parks (IOI21_parks)	C++17	5 / 100	61 ms	36740 KiB

parks

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const int Max = 2e5 + 7, Inf = 1e9 + 7;

void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);

struct DSU
{
    vector <int> link, size;

    int find(int x)
    {
        while(x != link[x]) x = link[x];
        return x;
    }

    bool unite(int a, int b)
    {
        a = find(a); b = find(b);
        if(a == b) return false;
        if(size[a] < size[b]) swap(a, b);
        link[b] = a; size[a] += size[b];
        return true;
    }

    DSU(int n)
    {
        link.assign(n + 1, 1);
        size.assign(n + 1, 1);
        for(int i = 0; i <= n; i++)
            link[i] = i;
    }
};

int construct_roads(vector<int> x, vector<int> y)
{
    vector <vector<int>> g(Max + 1, vector <int> (4, 0));

    int n = (int) x.size();

    for(int i = 0; i < n; i++)
        g[y[i]][x[i]/2] = i + 1;

    vector <int> u, v, a, b; map <int, map <int, bool>> mp;

    DSU St(n);

    for(int i = 0; i < Max; i++)
    {
        if(g[i][1] != 0 && g[i][2] != 0)
        {
            u.pb(g[i][1]); v.pb(g[i][2]);
            a.pb(i-1); b.pb(5); mp[i-1][5] = 1;
            St.unite(g[i][1], g[i][2]);
        }

        if(g[i][2] != 0 && g[i][3] != 0)
        {
            u.pb(g[i][2]); v.pb(g[i][3]);
            a.pb(i+1); b.pb(3); mp[i+1][3] = 1;
            St.unite(g[i][2], g[i][3]);
        }
    }

    for(int i = 0; i < Max; i++)
    {
        if(g[i][1] != 0 && g[i-2][1] != 0)
        {
            if(St.unite(g[i][1], g[i-2][1]))
            {
                u.pb(g[i][1]); v.pb(g[i-2][1]);
                a.pb(i-1); b.pb(1);
            }
        }

        if(g[i][3] != 0 && g[i-2][3] != 0)
        {
            if(St.unite(g[i][3], g[i-2][3]))
            {
                u.pb(g[i][3]); v.pb(g[i-2][3]);
                a.pb(i-1); b.pb(7);
            }
        }

        if(g[i][2] != 0 && g[i-2][2] != 0)
        {
            if(St.unite(g[i][2], g[i-2][2]))
            {
                u.pb(g[i][2]); v.pb(g[i-2][2]);
                a.pb(i-1);
                if(!mp[i-1][5]) b.pb(5);
                else b.pb(3);
            }
        }
    }

    if(St.size[St.find(1)] != n)return 0;
    else
    {
        for(int i = 0; i < (int) u.size(); i++)
            u[i]--, v[i]--;
        build(u, v, b, a);
        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