oj.uz

Submission #443080

# Submission time Handle Problem Language Result Execution time Memory
443080 2021-07-09T15:42:15 Z benedict0724 Fountain Parks (IOI21_parks) C++17
0 / 100
 462 ms 49212 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], CC = 0;

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);
    if(x != y) CC++;
    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;

    for(int i=0;i<n;i++) link[i] = i;
    for(int i=0;i<n;i++)
    {
        for(int j : adj[i])
        {
            if(_find(i) == _find(j)) continue;

            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] == 2 || (x[i] == 4 && 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;
            }
            _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);
        }
    }
    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 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4984 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Incorrect 462 ms 49212 KB Tree (a[99835], b[99835]) = (3, 135139) is not adjacent to edge between u[99835]=9 @(2, 135138) and v[99835]=34416 @(2, 135136)
10 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 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4984 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Incorrect 462 ms 49212 KB Tree (a[99835], b[99835]) = (3, 135139) is not adjacent to edge between u[99835]=9 @(2, 135138) and v[99835]=34416 @(2, 135136)
10 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 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4984 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Incorrect 462 ms 49212 KB Tree (a[99835], b[99835]) = (3, 135139) is not adjacent to edge between u[99835]=9 @(2, 135138) and v[99835]=34416 @(2, 135136)
10 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 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4984 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Incorrect 462 ms 49212 KB Tree (a[99835], b[99835]) = (3, 135139) is not adjacent to edge between u[99835]=9 @(2, 135138) and v[99835]=34416 @(2, 135136)
10 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 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4984 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Incorrect 462 ms 49212 KB Tree (a[99835], b[99835]) = (3, 135139) is not adjacent to edge between u[99835]=9 @(2, 135138) and v[99835]=34416 @(2, 135136)
10 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 Correct 3 ms 4940 KB Output is correct
3 Correct 3 ms 4940 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 3 ms 4940 KB Output is correct
6 Correct 3 ms 4940 KB Output is correct
7 Correct 3 ms 4984 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Incorrect 462 ms 49212 KB Tree (a[99835], b[99835]) = (3, 135139) is not adjacent to edge between u[99835]=9 @(2, 135138) and v[99835]=34416 @(2, 135136)
10 Halted 0 ms 0 KB -