답안 #1021045

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1021045	2024-07-12T13:15:31 Z	mdn2002	분수 공원 (IOI21_parks)	C++17	5 / 100	549 ms	113968 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;
    for (int i = 1; i <= n; i ++) mp[{x[i], y[i]}] = i;
    vector<int> u, v, a, b;

    map<pair<pair<int, int>, pair<int, int>>, int> connected;
    map<pair<int, int>, int> taken;
    for (int i = 1; i <= n; i ++) {
        if (x[i] == 2 && mp[{x[i], y[i] + 2}]) {
            connected[{{x[i], y[i]}, {x[i], y[i] + 2}}] = 1;
            u.push_back(i), v.push_back(mp[{x[i], y[i] + 2}]);
            a.push_back(x[i] - 1), b.push_back(y[i] + 1);
            taken[{x[i] - 1, y[i] + 1}] = 1;
            gr[i].push_back(mp[{x[i], y[i] + 2}]);
            gr[mp[{x[i], y[i] + 2}]].push_back(i);
        }
        else if (x[i] == 6 && mp[{x[i], y[i] + 2}]) {
            connected[{{x[i], y[i]}, {x[i], y[i] + 2}}] = 1;
            u.push_back(i), v.push_back(mp[{x[i], y[i] + 2}]);
            a.push_back(x[i] + 1), b.push_back(y[i] + 1);
            taken[{x[i] + 1, y[i] + 1}] = 1;
            gr[i].push_back(mp[{x[i], y[i] + 2}]);
            gr[mp[{x[i], y[i] + 2}]].push_back(i);
        }
        else if (x[i] == 4 && mp[{x[i], y[i] + 2}]) {
            connected[{{x[i], y[i]}, {x[i], y[i] + 2}}] = 1;
            u.push_back(i), v.push_back(mp[{x[i], y[i] + 2}]);

            if (y[i] % 4 == 2) a.push_back(x[i] + 1);
            else a.push_back(x[i] - 1);
            b.push_back(y[i] + 1);
            taken[{a.back(), b.back()}] = 1;

            gr[i].push_back(mp[{x[i], y[i] + 2}]);
            gr[mp[{x[i], y[i] + 2}]].push_back(i);
        }
    }
    for (int i = 1; i <= n; i ++) {
        if (x[i] == 2 && mp[{x[i] + 2, y[i]}]) {
            if (connected[{{x[i], y[i] - 2}, {x[i] + 2, y[i] - 2}}] == 1) continue;
            u.push_back(i), v.push_back(mp[{x[i] + 2, y[i]}]);
            if (taken[{x[i] + 1, y[i] + 1}] == 0) {
                a.push_back(x[i] + 1), b.push_back(y[i] + 1);
                taken[{x[i] + 1, y[i] + 1}] = 1;
            }
            else if (taken[{x[i] + 1, y[i] - 1}] == 0) {
                a.push_back(x[i] + 1), b.push_back(y[i] - 1);
                taken[{x[i] + 1, y[i] - 1}] = 1;
            }
            else assert(0);
            connected[{{x[i], y[i]}, {x[i] + 2, y[i]}}] = 1;

            gr[i].push_back(mp[{x[i] + 2, y[i]}]);
            gr[mp[{x[i] + 2, y[i]}]].push_back(i);
        }
        else if (x[i] == 6 && mp[{x[i] - 2, y[i]}]) {
            if (connected[{{x[i], y[i] - 2}, {x[i] - 2, y[i] - 2}}] == 1) continue;
            u.push_back(i), v.push_back(mp[{x[i] - 2, y[i]}]);
            if (taken[{x[i] - 1, y[i] + 1}] == 0) {
                a.push_back(x[i] - 1), b.push_back(y[i] + 1);
                taken[{x[i] - 1, y[i] + 1}] = 1;
            }
            else if (taken[{x[i] - 1, y[i] - 1}] == 0) {
                a.push_back(x[i] - 1), b.push_back(y[i] - 1);
                taken[{x[i] - 1, y[i] + 1}] = 1;
            }
            else assert(0);
            connected[{{x[i], y[i]}, {x[i] - 2, y[i]}}] = 1;

            gr[i].push_back(mp[{x[i] - 2, y[i]}]);
            gr[mp[{x[i] - 2, y[i]}]].push_back(i);
        }
    }
    for (int i = 0; i < u.size(); i ++) {
        u[i] --;
        v[i] --;
    }
    int num = 0;
    vector<int> vis(n + 1);
    function<void(int)> go = [&] (int x) {
        num ++;
        vis[x] = 1;
        for (auto u : gr[x]) {
            if (vis[u]) continue;
            go(u);
        }
    };
    go(1);

    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:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < u.size(); i ++) {
      |                     ~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	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	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	371 ms	44268 KB	Output is correct
10	Correct	14 ms	4720 KB	Output is correct
11	Correct	92 ms	24264 KB	Output is correct
12	Correct	32 ms	6996 KB	Output is correct
13	Correct	64 ms	17648 KB	Output is correct
14	Correct	2 ms	600 KB	Output is correct
15	Correct	3 ms	1116 KB	Output is correct
16	Correct	304 ms	41640 KB	Output is correct

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	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	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	371 ms	44268 KB	Output is correct
10	Correct	14 ms	4720 KB	Output is correct
11	Correct	92 ms	24264 KB	Output is correct
12	Correct	32 ms	6996 KB	Output is correct
13	Correct	64 ms	17648 KB	Output is correct
14	Correct	2 ms	600 KB	Output is correct
15	Correct	3 ms	1116 KB	Output is correct
16	Correct	304 ms	41640 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	600 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Runtime error	549 ms	113968 KB	Execution killed with signal 6
24	Halted	0 ms	0 KB	-

Subtask #3
0 / 15.0

#	결과	실행 시간	메모리	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	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	371 ms	44268 KB	Output is correct
10	Correct	14 ms	4720 KB	Output is correct
11	Correct	92 ms	24264 KB	Output is correct
12	Correct	32 ms	6996 KB	Output is correct
13	Correct	64 ms	17648 KB	Output is correct
14	Correct	2 ms	600 KB	Output is correct
15	Correct	3 ms	1116 KB	Output is correct
16	Correct	304 ms	41640 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	600 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Runtime error	549 ms	113968 KB	Execution killed with signal 6
24	Halted	0 ms	0 KB	-

Subtask #4
0 / 20.0

#	결과	실행 시간	메모리	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	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	371 ms	44268 KB	Output is correct
10	Correct	14 ms	4720 KB	Output is correct
11	Correct	92 ms	24264 KB	Output is correct
12	Correct	32 ms	6996 KB	Output is correct
13	Correct	64 ms	17648 KB	Output is correct
14	Correct	2 ms	600 KB	Output is correct
15	Correct	3 ms	1116 KB	Output is correct
16	Correct	304 ms	41640 KB	Output is correct
17	Incorrect	0 ms	344 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	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	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	371 ms	44268 KB	Output is correct
10	Correct	14 ms	4720 KB	Output is correct
11	Correct	92 ms	24264 KB	Output is correct
12	Correct	32 ms	6996 KB	Output is correct
13	Correct	64 ms	17648 KB	Output is correct
14	Correct	2 ms	600 KB	Output is correct
15	Correct	3 ms	1116 KB	Output is correct
16	Correct	304 ms	41640 KB	Output is correct
17	Incorrect	221 ms	35376 KB	Solution announced impossible, but it is possible.
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 30.0

#	결과	실행 시간	메모리	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	1 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	371 ms	44268 KB	Output is correct
10	Correct	14 ms	4720 KB	Output is correct
11	Correct	92 ms	24264 KB	Output is correct
12	Correct	32 ms	6996 KB	Output is correct
13	Correct	64 ms	17648 KB	Output is correct
14	Correct	2 ms	600 KB	Output is correct
15	Correct	3 ms	1116 KB	Output is correct
16	Correct	304 ms	41640 KB	Output is correct
17	Correct	0 ms	348 KB	Output is correct
18	Correct	1 ms	600 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	0 ms	348 KB	Output is correct
21	Correct	0 ms	348 KB	Output is correct
22	Correct	1 ms	348 KB	Output is correct
23	Runtime error	549 ms	113968 KB	Execution killed with signal 6
24	Halted	0 ms	0 KB	-

답안 #1021045

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