oj.uz

Submission #1039614

# Submission time Handle Problem Language Result Execution time Memory
1039614 2024-07-31T05:48:06 Z yanb Fountain Parks (IOI21_parks) C++17
5 / 100
 952 ms 108796 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) {
    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;
    follow(u, h, a, b, mid, pm, x, y);
}

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<int> a(n - 1), b(n - 1);
    for (int i = 0; i < cnt; i++) {
        follow(i, h, a, b, mid, pm, x, y);
    }

    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 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 1 ms 432 KB Output is correct
9 Correct 431 ms 55480 KB Output is correct
10 Correct 25 ms 5868 KB Output is correct
11 Correct 146 ms 30344 KB Output is correct
12 Correct 33 ms 8712 KB Output is correct
13 Correct 37 ms 8280 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 414 ms 53636 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 1 ms 432 KB Output is correct
9 Correct 431 ms 55480 KB Output is correct
10 Correct 25 ms 5868 KB Output is correct
11 Correct 146 ms 30344 KB Output is correct
12 Correct 33 ms 8712 KB Output is correct
13 Correct 37 ms 8280 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 414 ms 53636 KB Output is correct
17 Incorrect 1 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 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 1 ms 432 KB Output is correct
9 Correct 431 ms 55480 KB Output is correct
10 Correct 25 ms 5868 KB Output is correct
11 Correct 146 ms 30344 KB Output is correct
12 Correct 33 ms 8712 KB Output is correct
13 Correct 37 ms 8280 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 414 ms 53636 KB Output is correct
17 Incorrect 1 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 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 1 ms 432 KB Output is correct
9 Correct 431 ms 55480 KB Output is correct
10 Correct 25 ms 5868 KB Output is correct
11 Correct 146 ms 30344 KB Output is correct
12 Correct 33 ms 8712 KB Output is correct
13 Correct 37 ms 8280 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 414 ms 53636 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 Incorrect 952 ms 105424 KB a[0] = 0 is not an odd integer
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 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 1 ms 432 KB Output is correct
9 Correct 431 ms 55480 KB Output is correct
10 Correct 25 ms 5868 KB Output is correct
11 Correct 146 ms 30344 KB Output is correct
12 Correct 33 ms 8712 KB Output is correct
13 Correct 37 ms 8280 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 414 ms 53636 KB Output is correct
17 Incorrect 910 ms 108796 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 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 1 ms 432 KB Output is correct
9 Correct 431 ms 55480 KB Output is correct
10 Correct 25 ms 5868 KB Output is correct
11 Correct 146 ms 30344 KB Output is correct
12 Correct 33 ms 8712 KB Output is correct
13 Correct 37 ms 8280 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 414 ms 53636 KB Output is correct
17 Incorrect 1 ms 348 KB Wrong answer detected in grader
18 Halted 0 ms 0 KB -