Submission #1021080

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1021080	2024-07-12T13:46:20 Z	mdn2002	Fountain Parks (IOI21_parks)	C++17	5 / 100	715 ms	102060 KB

parks

/*
Mayoeba Yabureru
*/
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
static vector<int> _u, _v, _a, _b;

int construct_roads(vector<int> x, vector<int> y) {
    int n = x.size();
    vector<vector<int>> gr(n + 1);
    x.insert(x.begin(), 0);
    y.insert(y.begin(), 0);
    map<pair<int, int>, int> mp;
    map<pair<int, int>, pair<int, int>> mpp;
    for (int i = 1; i <= n; i ++) mp[{x[i], y[i]}] = i;
    vector<int> u, v, a, b;

    map<pair<int, int>, int> taken;

    for (int i = 1; i <= n; i ++) {
        if (mp[{x[i] + 2, y[i]}]) {
            u.push_back(i), v.push_back(mp[{x[i] + 2, y[i]}]);
            gr[i].push_back(mp[{x[i] + 2, y[i]}]);
            gr[mp[{x[i] + 2, y[i]}]].push_back(i);
        }
        if (mp[{x[i], y[i] + 2}]) {
            u.push_back(i), v.push_back(mp[{x[i], y[i] + 2}]);
            gr[i].push_back(mp[{x[i], y[i] + 2}]);
            gr[mp[{x[i], y[i] + 2}]].push_back(i);
        }
    }

    int num = 0, st = 0;
    vector<int> vis(n + 1);
    for (int i = 1; i <= n; i ++) {
        if (gr[i].size() == 1) {
            st = i;
            break;
        }
    }
    function<void(int)> go = [&] (int v) {
        num ++;
        vis[v] = 1;
        for (auto u : gr[v]) {
            if (vis[u]) continue;
            if (x[v] != x[u]) {
                int xx = v, uu = u;
                if (x[xx] > x[uu]) swap(xx, uu);
                if (taken[{x[xx] + 1, y[xx] + 1}] == 0) {
                    mpp[{xx, uu}] = {x[xx] + 1, y[xx] + 1};
                    taken[{x[xx] + 1, y[xx] + 1}] = 1;
                }
                else if (taken[{x[xx] + 1, y[xx] - 1}] == 0) {
                    mpp[{xx, uu}] = {x[xx] + 1, y[xx] + 1};
                    taken[{x[xx] + 1, y[xx] - 1}] = 1;
                }
                else assert(0);
            }
            else {
                int xx = v, uu = u;
                if (y[xx] > y[uu]) swap(xx, uu);
                if (taken[{x[xx] + 1, y[xx] + 1}] == 0) {
                    mpp[{xx, uu}] = {x[xx] + 1, y[xx] + 1};
                    taken[{x[xx] + 1, y[xx] + 1}] = 1;
                }
                else if (taken[{x[xx] - 1, y[xx] + 1}] == 0) {
                    mpp[{xx, uu}] = {x[xx] - 1, y[xx] + 1};
                    taken[{x[xx] - 1, y[xx] + 1}] = 1;
                }
                else assert(0);
            }
            go(u);
        }
    };
    go(st);
    for (int i = 0; i < u.size(); i ++) {
        a.push_back(mpp[{u[i], v[i]}].first);
        b.push_back(mpp[{u[i], v[i]}].second);
        u[i] --;
        v[i] --;
    }
    if (num == n) {
        build(u, v, a, b);
        return 1;
    }
    return 0;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:77:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for (int i = 0; i < u.size(); i ++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	299 ms	50968 KB	Output is correct
10	Correct	14 ms	5720 KB	Output is correct
11	Correct	91 ms	27560 KB	Output is correct
12	Correct	22 ms	8016 KB	Output is correct
13	Correct	61 ms	18672 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	2 ms	1088 KB	Output is correct
16	Correct	341 ms	51092 KB	Output is correct

Subtask #2
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	299 ms	50968 KB	Output is correct
10	Correct	14 ms	5720 KB	Output is correct
11	Correct	91 ms	27560 KB	Output is correct
12	Correct	22 ms	8016 KB	Output is correct
13	Correct	61 ms	18672 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	2 ms	1088 KB	Output is correct
16	Correct	341 ms	51092 KB	Output is correct
17	Incorrect	0 ms	348 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	299 ms	50968 KB	Output is correct
10	Correct	14 ms	5720 KB	Output is correct
11	Correct	91 ms	27560 KB	Output is correct
12	Correct	22 ms	8016 KB	Output is correct
13	Correct	61 ms	18672 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	2 ms	1088 KB	Output is correct
16	Correct	341 ms	51092 KB	Output is correct
17	Incorrect	0 ms	348 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	299 ms	50968 KB	Output is correct
10	Correct	14 ms	5720 KB	Output is correct
11	Correct	91 ms	27560 KB	Output is correct
12	Correct	22 ms	8016 KB	Output is correct
13	Correct	61 ms	18672 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	2 ms	1088 KB	Output is correct
16	Correct	341 ms	51092 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	0 ms	348 KB	Output is correct
19	Correct	0 ms	348 KB	Output is correct
20	Correct	633 ms	96088 KB	Output is correct
21	Incorrect	715 ms	102060 KB	Tree @(5, 5) appears more than once: for edges on positions 113946 and 113947
22	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	299 ms	50968 KB	Output is correct
10	Correct	14 ms	5720 KB	Output is correct
11	Correct	91 ms	27560 KB	Output is correct
12	Correct	22 ms	8016 KB	Output is correct
13	Correct	61 ms	18672 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	2 ms	1088 KB	Output is correct
16	Correct	341 ms	51092 KB	Output is correct
17	Incorrect	493 ms	58272 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	299 ms	50968 KB	Output is correct
10	Correct	14 ms	5720 KB	Output is correct
11	Correct	91 ms	27560 KB	Output is correct
12	Correct	22 ms	8016 KB	Output is correct
13	Correct	61 ms	18672 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	2 ms	1088 KB	Output is correct
16	Correct	341 ms	51092 KB	Output is correct
17	Incorrect	0 ms	348 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Submission #1021080

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 10.0

Subtask #3 0 / 15.0

Subtask #4 0 / 20.0

Subtask #5 0 / 20.0

Subtask #6 0 / 30.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 10.0

Subtask #3
0 / 15.0

Subtask #4
0 / 20.0

Subtask #5
0 / 20.0

Subtask #6
0 / 30.0