oj.uz

Submission #1059029

# Submission time Handle Problem Language Result Execution time Memory
1059029 2024-08-14T16:11:26 Z qwusha Fountain Parks (IOI21_parks) C++17
15 / 100
 3500 ms 169908 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
typedef long double ld;
const ld eps = 1e-8;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const ll inf = 1e18;
const ll mod = 1e9 + 7;

#include "parks.h"


vector<vector<int>> g;
vector<int> u, v, a, b;

vector<int> used;

void dfs(int ver) {
    used[ver] = 1;
    for (auto nod : g[ver]) {
        if (!used[nod]) {
            u.push_back(ver);
            v.push_back(nod);
            dfs(nod);
        }
    }
}



int construct_roads(vector<int> x, vector<int> y) {
    bool fir = 1, sec = 1, thi = 1;
    int n = x.size();
    for (int i = 0; i < n; i++) {
        if (x[i] != 2)
            fir = 0;
    }
    map<pair<int, int>, int> mp;
    for (int i = 0; i < n; i++) {
        mp[{x[i], y[i]}] = i;
    }
    g.resize(n);
    for (int i = 0; i < n; i++) {
        if (mp.find({x[i] - 2, y[i]}) != mp.end()) {
            g[i].push_back(mp[{x[i] - 2, y[i]}]);
        }
        if (mp.find({x[i] + 2, y[i]}) != mp.end()) {
            g[i].push_back(mp[{x[i] + 2, y[i]}]);
        }
        if (mp.find({x[i], y[i] - 2}) != mp.end()) {
            g[i].push_back(mp[{x[i], y[i] - 2}]);
        }
        if (mp.find({x[i], y[i] + 2}) != mp.end()) {
            g[i].push_back(mp[{x[i], y[i] + 2}]);
        }
    }
    used.resize(n);
    dfs(0);
    bool ch = 1;
    for (int i = 0; i < n; i++) {
        if (!used[i])
            ch = 0;
    }
    if (!ch)
        return 0;
    map<pair<int, int>, int> bench;
    map<pair<int, int>, set<int>> want;
    set<vector<int>> ben;
    for (int i = 0; i < v.size(); i++) {
        if (x[v[i]] == x[u[i]]) {
            want[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}].insert(i);
            want[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}].insert(i);
            bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}]++;
            bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}]++;
        } else {
            want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}].insert(i);
            want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}].insert(i);
            bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}]++;
            bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}]++;
        }
    }
    for (auto [pa, cnt] : bench) {
        ben.insert({cnt, pa.fi, pa.se});
    }
    a.resize(n - 1);
    b.resize(n - 1);
    while(!ben.empty()) {
        auto cur = *ben.begin();
        int i = *want[{cur[1], cur[2]}].begin();
        if (cur[0] > 1) {
            while(1) {
                
            }
        }
        a[i] = cur[1];
        b[i] = cur[2];
        if (x[v[i]] == x[u[i]]) {
            want[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}].erase(i);
            want[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}].erase(i);
            ben.erase({bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] + 1,(y[v[i]] + y[u[i]]) / 2});
            ben.erase({bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2});
            bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}]--;
            bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}]--;
            if (bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}] > 0) {
                ben.insert({bench[{x[v[i]] + 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] + 1,(y[v[i]] + y[u[i]]) / 2});
            }
            if (bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}] > 0) {
                ben.insert({bench[{x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2}], x[v[i]] - 1, (y[v[i]] + y[u[i]]) / 2});
            }
        } else {
            want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}].erase(i);
            want[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}].erase(i);
            ben.erase({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}],(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1 });
            ben.erase({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}], (x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1});
            bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}]--;
            bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}]--;
            if ( bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}] > 0) {
                ben.insert({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1}],(x[v[i]] + x[u[i]]) / 2, y[v[i]] + 1 });
            }
            if (bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}] > 0) {
                ben.insert({bench[{(x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1}], (x[v[i]] + x[u[i]]) / 2, y[v[i]] - 1});
            }
        }
    }
    build(u, v, a, b);
    return 1;

}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:71:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for (int i = 0; i < v.size(); i++) {
      |                     ~~^~~~~~~~~~
parks.cpp:34:10: warning: variable 'fir' set but not used [-Wunused-but-set-variable]
   34 |     bool fir = 1, sec = 1, thi = 1;
      |          ^~~
parks.cpp:34:19: warning: unused variable 'sec' [-Wunused-variable]
   34 |     bool fir = 1, sec = 1, thi = 1;
      |                   ^~~
parks.cpp:34:28: warning: unused variable 'thi' [-Wunused-variable]
   34 |     bool fir = 1, sec = 1, thi = 1;
      |                            ^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 352 ms 84700 KB Output is correct
10 Correct 25 ms 8796 KB Output is correct
11 Correct 181 ms 46200 KB Output is correct
12 Correct 37 ms 12880 KB Output is correct
13 Correct 28 ms 9044 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 364 ms 82024 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 352 ms 84700 KB Output is correct
10 Correct 25 ms 8796 KB Output is correct
11 Correct 181 ms 46200 KB Output is correct
12 Correct 37 ms 12880 KB Output is correct
13 Correct 28 ms 9044 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 364 ms 82024 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 436 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 835 ms 118384 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 2 ms 928 KB Output is correct
26 Correct 2 ms 832 KB Output is correct
27 Correct 3 ms 860 KB Output is correct
28 Correct 281 ms 48044 KB Output is correct
29 Correct 466 ms 70264 KB Output is correct
30 Correct 633 ms 95168 KB Output is correct
31 Correct 816 ms 117360 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 3 ms 860 KB Output is correct
45 Correct 363 ms 67216 KB Output is correct
46 Correct 556 ms 97592 KB Output is correct
47 Correct 582 ms 97212 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 352 ms 84700 KB Output is correct
10 Correct 25 ms 8796 KB Output is correct
11 Correct 181 ms 46200 KB Output is correct
12 Correct 37 ms 12880 KB Output is correct
13 Correct 28 ms 9044 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 364 ms 82024 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 436 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 835 ms 118384 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 2 ms 928 KB Output is correct
26 Correct 2 ms 832 KB Output is correct
27 Correct 3 ms 860 KB Output is correct
28 Correct 281 ms 48044 KB Output is correct
29 Correct 466 ms 70264 KB Output is correct
30 Correct 633 ms 95168 KB Output is correct
31 Correct 816 ms 117360 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 3 ms 860 KB Output is correct
45 Correct 363 ms 67216 KB Output is correct
46 Correct 556 ms 97592 KB Output is correct
47 Correct 582 ms 97212 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 432 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 936 ms 116300 KB Output is correct
56 Execution timed out 3571 ms 348 KB Time limit exceeded
57 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 352 ms 84700 KB Output is correct
10 Correct 25 ms 8796 KB Output is correct
11 Correct 181 ms 46200 KB Output is correct
12 Correct 37 ms 12880 KB Output is correct
13 Correct 28 ms 9044 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 364 ms 82024 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 728 ms 120456 KB Output is correct
21 Correct 704 ms 117656 KB Output is correct
22 Correct 712 ms 116164 KB Output is correct
23 Correct 619 ms 140832 KB Output is correct
24 Correct 189 ms 22872 KB Output is correct
25 Correct 283 ms 29012 KB Output is correct
26 Correct 241 ms 28944 KB Output is correct
27 Correct 724 ms 157296 KB Output is correct
28 Correct 704 ms 157292 KB Output is correct
29 Correct 832 ms 157292 KB Output is correct
30 Correct 859 ms 157036 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Execution timed out 3592 ms 8944 KB Time limit exceeded
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 352 ms 84700 KB Output is correct
10 Correct 25 ms 8796 KB Output is correct
11 Correct 181 ms 46200 KB Output is correct
12 Correct 37 ms 12880 KB Output is correct
13 Correct 28 ms 9044 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 364 ms 82024 KB Output is correct
17 Correct 759 ms 169908 KB Output is correct
18 Correct 757 ms 169096 KB Output is correct
19 Correct 726 ms 120324 KB Output is correct
20 Execution timed out 3549 ms 122480 KB Time limit exceeded
21 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 352 ms 84700 KB Output is correct
10 Correct 25 ms 8796 KB Output is correct
11 Correct 181 ms 46200 KB Output is correct
12 Correct 37 ms 12880 KB Output is correct
13 Correct 28 ms 9044 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 364 ms 82024 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 436 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 835 ms 118384 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 2 ms 928 KB Output is correct
26 Correct 2 ms 832 KB Output is correct
27 Correct 3 ms 860 KB Output is correct
28 Correct 281 ms 48044 KB Output is correct
29 Correct 466 ms 70264 KB Output is correct
30 Correct 633 ms 95168 KB Output is correct
31 Correct 816 ms 117360 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 344 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 1 ms 604 KB Output is correct
44 Correct 3 ms 860 KB Output is correct
45 Correct 363 ms 67216 KB Output is correct
46 Correct 556 ms 97592 KB Output is correct
47 Correct 582 ms 97212 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 432 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 348 KB Output is correct
55 Correct 936 ms 116300 KB Output is correct
56 Execution timed out 3571 ms 348 KB Time limit exceeded
57 Halted 0 ms 0 KB -