oj.uz

Submission #443091

# Submission time Handle Problem Language Result Execution time Memory
443091 2021-07-09T16:01:52 Z benedict0724 Fountain Parks (IOI21_parks) C++17
5 / 100
 1004 ms 94664 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 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] == 6 || (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;
        }
    }

    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.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 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 395 ms 48816 KB Output is correct
10 Correct 24 ms 9420 KB Output is correct
11 Correct 126 ms 28992 KB Output is correct
12 Correct 34 ms 11664 KB Output is correct
13 Correct 75 ms 18116 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 403 ms 45816 KB Output is correct

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 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 395 ms 48816 KB Output is correct
10 Correct 24 ms 9420 KB Output is correct
11 Correct 126 ms 28992 KB Output is correct
12 Correct 34 ms 11664 KB Output is correct
13 Correct 75 ms 18116 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 403 ms 45816 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct
23 Incorrect 1004 ms 78948 KB Tree @(3, 5) appears more than once: for edges on positions 111193 and 111194
24 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 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 395 ms 48816 KB Output is correct
10 Correct 24 ms 9420 KB Output is correct
11 Correct 126 ms 28992 KB Output is correct
12 Correct 34 ms 11664 KB Output is correct
13 Correct 75 ms 18116 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 403 ms 45816 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct
23 Incorrect 1004 ms 78948 KB Tree @(3, 5) appears more than once: for edges on positions 111193 and 111194
24 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 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 395 ms 48816 KB Output is correct
10 Correct 24 ms 9420 KB Output is correct
11 Correct 126 ms 28992 KB Output is correct
12 Correct 34 ms 11664 KB Output is correct
13 Correct 75 ms 18116 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 403 ms 45816 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Incorrect 867 ms 82264 KB Tree @(7, 199995) appears more than once: for edges on positions 2 and 100001
21 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 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 395 ms 48816 KB Output is correct
10 Correct 24 ms 9420 KB Output is correct
11 Correct 126 ms 28992 KB Output is correct
12 Correct 34 ms 11664 KB Output is correct
13 Correct 75 ms 18116 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 403 ms 45816 KB Output is correct
17 Correct 975 ms 94664 KB Output is correct
18 Correct 950 ms 88528 KB Output is correct
19 Incorrect 905 ms 79256 KB Tree @(7, 50005) appears more than once: for edges on positions 23802 and 123800
20 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 4940 KB Output is correct
8 Correct 3 ms 4940 KB Output is correct
9 Correct 395 ms 48816 KB Output is correct
10 Correct 24 ms 9420 KB Output is correct
11 Correct 126 ms 28992 KB Output is correct
12 Correct 34 ms 11664 KB Output is correct
13 Correct 75 ms 18116 KB Output is correct
14 Correct 4 ms 5196 KB Output is correct
15 Correct 6 ms 5452 KB Output is correct
16 Correct 403 ms 45816 KB Output is correct
17 Correct 3 ms 4940 KB Output is correct
18 Correct 3 ms 4940 KB Output is correct
19 Correct 3 ms 4940 KB Output is correct
20 Correct 3 ms 4940 KB Output is correct
21 Correct 3 ms 4940 KB Output is correct
22 Correct 3 ms 4940 KB Output is correct
23 Incorrect 1004 ms 78948 KB Tree @(3, 5) appears more than once: for edges on positions 111193 and 111194
24 Halted 0 ms 0 KB -