Submission #443089

#	Time	Username	Problem	Language	Result	Execution time	Memory
443089		benedict0724	Fountain Parks (IOI21_parks)	C++17	45 / 100	1079 ms	94620 KiB

parks

#include "parks.h"

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

map<pair<int, int>, int> M, M2;
vector<int> adj[200000];
bool counting[200000];

vector<pair<int, int>> E;

int cnt = 0;
void count_fountains(int x)
{
    cnt++;
    counting[x] = true;
    for(int i : adj[x])
    {
        if(counting[i]) continue;
        count_fountains(i);
        E.push_back({x, i});
    }
}

int construct_roads(vector<int> x, vector<int> y) {

    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }

    int n = x.size();
    vector<int> u, v, a, b;
    for(int i=0;i<n;i++)
        M[{x[i], y[i]}] = i+1;

    for(int i=0;i<n;i++)
    {
        if(M[{x[i]+2, y[i]}]) adj[i].push_back(M[{x[i]+2, y[i]}]-1);
        if(M[{x[i], y[i]+2}]) adj[i].push_back(M[{x[i], y[i]+2}]-1);
        if(M[{x[i]-2, y[i]}]) adj[i].push_back(M[{x[i]-2, y[i]}]-1);
        if(M[{x[i], y[i]-2}]) adj[i].push_back(M[{x[i], y[i]-2}]-1);
    }

    count_fountains(0);
    if(cnt < n) return 0;

    for(auto U : E)
    {
        int i = U.first, j = U.second;
        if(y[i] == y[j]) continue;
        if(y[i] > y[j]) swap(i, j);
        u.push_back(i);
        v.push_back(j);
        b.push_back(y[i]+1);
        if((x[i]+y[i])%4 == 0)
        {
            a.push_back(x[i]+1);
            M2[{x[i]+1, y[i]+1}] = 1;
        }
        else
        {
            a.push_back(x[i]-1);
            M2[{x[i]-1, y[i]+1}] = 1;
        }
    }

    for(auto U : E)
    {
        int i = U.first, j = U.second;
        if(y[i] != y[j]) continue;
        if(x[i] > x[j]) swap(i, j);
        u.push_back(i);
        v.push_back(j);
        a.push_back(x[i]+1);
        if(M2[{x[i]+1, y[i]+1}]) b.push_back(y[i]-1);
        else b.push_back(y[i]+1);
    }

    build(u, v, a, b);
    return 1;
}

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