oj.uz

Submission #1039666

# Submission time Handle Problem Language Result Execution time Memory
1039666 2024-07-31T07:12:48 Z yanb Fountain Parks (IOI21_parks) C++17
5 / 100
 820 ms 211124 KB 
#include <bits/stdc++.h>
    
using namespace std;
    
//#define int long long
//#define pii pair<long long, long long>
#define pii pair<int, int>
#define pib pair<int, bool>
#define fi first
#define se second
    
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b);
    
void dfs(int v, vector<vector<int>> &g, vector<bool> &uu) {
    if (uu[v]) return;
    uu[v] = 1;
    for (int u : g[v]) dfs(u, g, uu);
}
    
void follow(int v, vector<vector<int>> &h, vector<int> &a, vector<int> &b, map<pii, int> &mid, 
vector<pii> &pm, vector<int> &x, vector<int> &y, vector<bool> &mdok) {
    if (h[v].empty()) return;
    int u = h[v].back();
    //cout << "Erasing " << pm[v].fi << "," << pm[v].se << " ~ " << pm[u].fi << "," << pm[u].se << "\n";
    h[v].erase(remove(h[v].begin(), h[v].end(), u), h[v].end());
    h[u].erase(remove(h[u].begin(), h[u].end(), v), h[u].end());
    int pd = mid[{(pm[v].fi + pm[u].fi) / 2, (pm[v].se + pm[u].se) / 2}];
    a[pd] = pm[v].fi;
    b[pd] = pm[v].se;
    mdok[pd] = 1;
    follow(u, h, a, b, mid, pm, x, y, mdok);
}
    
int do_tree(vector<int> x, vector<int> y) {
    int n = x.size();
    map<pii, int> id, mid;
    for (int i = 0; i < n; i++) {
        id[{x[i], y[i]}] = i;
    }
    
    vector<vector<int>> g(n);
    for (int i = 0; i < n; i++) {
        if (id.count({x[i] + 2, y[i]})) g[i].push_back(id[{x[i] + 2, y[i]}]);
        if (id.count({x[i] - 2, y[i]})) g[i].push_back(id[{x[i] - 2, y[i]}]);
        if (id.count({x[i], y[i] + 2})) g[i].push_back(id[{x[i], y[i] + 2}]);
        if (id.count({x[i], y[i] - 2})) g[i].push_back(id[{x[i], y[i] - 2}]);
    }
    
    vector<bool> uu(n);
    dfs(0, g, uu);
    for (int i = 0; i < n; i++) {
        if (!uu[i]) return 0;
    }
    
    vector<int> bu, bv;
    int cnt = 0;
    for (int u = 0; u < n; u++) {
        for (int v : g[u]) {
            if (v > u) {
                bv.push_back(v);
                bu.push_back(u);
                mid[{(x[v] + x[u]) / 2, (y[v] + y[u]) / 2}] = cnt;
                cnt++;
            }
        }
    }
    
    cnt = 0;
    map<pii, int> mp;
    vector<pii> pm;
    vector<vector<int>> h;
    for (int v = 0; v < n; v++) {
        for (int u : g[v]) {
            int xm = (x[v] + x[u]) / 2, ym = (y[v] + y[u]) / 2;
            pii p = {xm + (ym - y[v]), ym + (xm - x[v])}; 
            pii q = {xm + (ym - y[u]), ym + (xm - x[u])}; 
            if (!mp.count(p)) {
                mp[p] = cnt;
                h.push_back({});
                pm.push_back(p);
                cnt++;
            }
            if (!mp.count(q)) {
                mp[q] = cnt;
                h.push_back({});
                pm.push_back(q);
                cnt++;
            }
            h[mp[p]].push_back(mp[q]);
        }
    }
    
    vector<bool> mdok(n - 1);
    vector<int> a(n - 1), b(n - 1);
    for (int i = 0; i < cnt; i++) {
        follow(i, h, a, b, mid, pm, x, y, mdok);
    }

    for (int i = 0; i < n - 1; i++) {
        if (!mdok[i]) {
            throw -1;
        }
    }
    
    build(bu, bv, a, b);
    
    return 1;
}
    
int construct_roads(vector<int> x, vector<int> y) {
    return do_tree(x, y);
}
    
#ifdef LOCAL
void build(vector<int> u, vector<int> v, vector<int> a, vector<int> b) {
    int n = u.size();
    for (int i = 0; i < n; i++) cout << u[i] << " ";
    cout << "\n";
    for (int i = 0; i < n; i++) cout << v[i] << " ";
    cout << "\n";
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << "\n";
    for (int i = 0; i < n; i++) cout << b[i] << " ";
    cout << "\n";
}
    
signed main() {
    //construct_roads({2, 4}, {2, 4});
    construct_roads({4, 4, 6, 4, 2, 4, 2, 4, 6, 6, 8, 8}, {4, 6, 4, 2, 4, 8, 8, 10, 10, 12, 8, 10});
    //construct_roads({4, 4, 6, 4, 2}, {4, 6, 4, 2, 4});
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 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 408 ms 55612 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 133 ms 30204 KB Output is correct
12 Correct 32 ms 8712 KB Output is correct
13 Correct 38 ms 8272 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 405 ms 53692 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 1 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 408 ms 55612 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 133 ms 30204 KB Output is correct
12 Correct 32 ms 8712 KB Output is correct
13 Correct 38 ms 8272 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 405 ms 53692 KB Output is correct
17 Incorrect 0 ms 348 KB Wrong answer detected in grader
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 1 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 408 ms 55612 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 133 ms 30204 KB Output is correct
12 Correct 32 ms 8712 KB Output is correct
13 Correct 38 ms 8272 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 405 ms 53692 KB Output is correct
17 Incorrect 0 ms 348 KB Wrong answer detected in grader
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 1 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 408 ms 55612 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 133 ms 30204 KB Output is correct
12 Correct 32 ms 8712 KB Output is correct
13 Correct 38 ms 8272 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 405 ms 53692 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 436 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Runtime error 790 ms 211124 KB Execution killed with signal 6
21 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 1 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 408 ms 55612 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 133 ms 30204 KB Output is correct
12 Correct 32 ms 8712 KB Output is correct
13 Correct 38 ms 8272 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 405 ms 53692 KB Output is correct
17 Incorrect 820 ms 108944 KB Wrong answer detected in grader
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 1 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 408 ms 55612 KB Output is correct
10 Correct 19 ms 5908 KB Output is correct
11 Correct 133 ms 30204 KB Output is correct
12 Correct 32 ms 8712 KB Output is correct
13 Correct 38 ms 8272 KB Output is correct
14 Correct 1 ms 344 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 405 ms 53692 KB Output is correct
17 Incorrect 0 ms 348 KB Wrong answer detected in grader
18 Halted 0 ms 0 KB -