oj.uz

Submission #443043

# Submission time Handle Problem Language Result Execution time Memory
443043 2021-07-09T14:09:15 Z benedict0724 Fountain Parks (IOI21_parks) C++17
0 / 100
 3 ms 4940 KB 
#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 link[200002];

int _find(int x)
{
    if(x == link[x]) return x;
    return link[x] = _find(link[x]);
}

void _unite(int x, int y)
{
    x = _find(x); y = _find(y);
    link[x] = y;
}

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;

    int MAX = 0;
    for(int i=0;i<n;i++) MAX = max(MAX, x[i]);

    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]-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], y[i]-2}]) adj[i].push_back(M[{x[i], y[i]-2}]-1);
    }

    count_fountains(0);

    if(cnt < n) return 0;

    if(MAX <= 6)
    {
        for(int i=0;i<n;i++) link[i] = i;
        for(int i=0;i<n;i++)
        {
            for(int j : adj[i])
            {
                if(y[i] == y[j]) continue;
                if(y[i] < y[j])
                {
                    u.push_back(i);
                    v.push_back(j);
                    b.push_back(y[i] + 1);
                    if(x[i] <= 4)
                    {
                        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;
                    }

                    _unite(i, j);
                }
            }
        }
        for(int i=0;i<n;i++)
        {
            for(int j : adj[i])
            {
                if(_find(i) == _find(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);

                _unite(i, j);
            }
        }

        return 1;
    }

    for(auto U : E)
    {
        int i = U.first, j = U.second;
        if(x[i] == x[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((x[i]+y[i])%4 == 0)
        {
            b.push_back(y[i]+1);
            M2[{x[i]+1, y[i]+1}] = 1;
        }
        else
        {
            b.push_back(y[i]-1);
            M2[{x[i]+1, y[i]-1}] = 1;
        }
    }

    for(auto U : E)
    {
        int i = U.first, j = U.second;
        if(x[i] != x[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(M2[{x[i]+1, y[i]+1}]) a.push_back(x[i]-1);
        else a.push_back(x[i]+1);
    }

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Incorrect 3 ms 4940 KB Wrong answer detected in grader
3 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Incorrect 3 ms 4940 KB Wrong answer detected in grader
3 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Incorrect 3 ms 4940 KB Wrong answer detected in grader
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Incorrect 3 ms 4940 KB Wrong answer detected in grader
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Incorrect 3 ms 4940 KB Wrong answer detected in grader
3 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Incorrect 3 ms 4940 KB Wrong answer detected in grader
3 Halted 0 ms 0 KB -