oj.uz

Submission #617534

# Submission time Handle Problem Language Result Execution time Memory
617534 2022-08-01T12:00:39 Z happypotato Fountain Parks (IOI21_parks) C++17
5 / 100
 413 ms 31912 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
const int mxN = 2e5 + 1;
const int dx[mxN] = {0, 1, 0, -1}, dy[mxN] = {1, 0, -1, 0};
bool vis[mxN];
pair<pii, int> pts[mxN];
pii opts[mxN];
map<pii, int> allpts;
int n;
bool CheckConnected() {
    queue<pii> q;
    set<pii> track;
    q.push(pts[0].ff);
    track.insert(pts[0].ff);
    while (!q.empty()) {
        pii cur = q.front();
        q.pop();
        for (int k = 0; k < 4; k++) {
            int nx = cur.ff + dx[k] * 2;
            int ny = cur.ss + dy[k] * 2;
            if (allpts.find({nx, ny}) != allpts.end() && track.find({nx, ny}) == track.end()) {
                q.push({nx, ny});
                track.insert({nx, ny});
            }
        }
    }
    return (int(track.size()) == n);
}
void st12() {
    vector<pii> edge;
    vis[pts[0].ss] = true;
    for (int i = 0; i < n; i++) {
        if (allpts.find({pts[i].ff.ff, pts[i].ff.ss + 2}) != allpts.end()) {
            int v = allpts[{pts[i].ff.ff, pts[i].ff.ss + 2}];
            if (!vis[v]) {
                edge.pb({pts[i].ss, v});
                vis[v] = true;
            }
        }
        if (pts[i].ff.ff == 4 && allpts.find({2, pts[i].ff.ss}) != allpts.end()) {
            int v = allpts[{2, pts[i].ff.ss}];
            if (!vis[v]) {
                edge.pb({pts[i].ss, v});
                vis[v] = true;
            }
        }
    }
    int m = edge.size();
    vector<int> u(m), v(m), a(m), b(m);
    for (int i = 0; i < m; i++) {
        u[i] = edge[i].ff;
        v[i] = edge[i].ss;
        if (opts[u[i]].ff == opts[v[i]].ff) {
            a[i] = (opts[u[i]].ff == 2 ? 1 : 5);
            b[i] = ((opts[u[i]].ss + opts[v[i]].ss) >> 1);
        } else {
            a[i] = 3;
            b[i] = opts[u[i]].ss - 1;
        }
    }
    build(u, v, a, b);
    return;
}
void st3() {

}
int construct_roads(vector<int> ox, vector<int> oy) {
    n = ox.size();
    int minx = 1e9;
    for (int i = 0; i < n; i++) {
        pts[i] = {{ox[i], oy[i]}, i};
        opts[i] = pts[i].ff;
        allpts[pts[i].ff] = i;
        minx = min(minx, pts[i].ff.ff);
    }
    sort(pts, pts + n);
    // for (int i = 0; i < n; i++) {
    //     cout << pts[i].ff.ff << ' ' << pts[i].ff.ss << ' ' << pts[i].ss << endl;
    // }
    if (!CheckConnected()) return 0;
    if (minx == 2 || minx == 4) st12();
    else if (minx == 6) st3();
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 174 ms 17856 KB Output is correct
10 Correct 13 ms 2132 KB Output is correct
11 Correct 87 ms 9776 KB Output is correct
12 Correct 21 ms 2936 KB Output is correct
13 Correct 36 ms 6388 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 172 ms 18452 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 174 ms 17856 KB Output is correct
10 Correct 13 ms 2132 KB Output is correct
11 Correct 87 ms 9776 KB Output is correct
12 Correct 21 ms 2936 KB Output is correct
13 Correct 36 ms 6388 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 172 ms 18452 KB Output is correct
17 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 174 ms 17856 KB Output is correct
10 Correct 13 ms 2132 KB Output is correct
11 Correct 87 ms 9776 KB Output is correct
12 Correct 21 ms 2936 KB Output is correct
13 Correct 36 ms 6388 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 172 ms 18452 KB Output is correct
17 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 174 ms 17856 KB Output is correct
10 Correct 13 ms 2132 KB Output is correct
11 Correct 87 ms 9776 KB Output is correct
12 Correct 21 ms 2936 KB Output is correct
13 Correct 36 ms 6388 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 172 ms 18452 KB Output is correct
17 Incorrect 1 ms 320 KB Wrong answer detected in grader
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 174 ms 17856 KB Output is correct
10 Correct 13 ms 2132 KB Output is correct
11 Correct 87 ms 9776 KB Output is correct
12 Correct 21 ms 2936 KB Output is correct
13 Correct 36 ms 6388 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 172 ms 18452 KB Output is correct
17 Incorrect 413 ms 31912 KB Tree (a[50000], b[50000]) = (5, 3) is not adjacent to edge between u[50000]=138413 @(100002, 2) and v[50000]=87394 @(100002, 4)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 308 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 174 ms 17856 KB Output is correct
10 Correct 13 ms 2132 KB Output is correct
11 Correct 87 ms 9776 KB Output is correct
12 Correct 21 ms 2936 KB Output is correct
13 Correct 36 ms 6388 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 472 KB Output is correct
16 Correct 172 ms 18452 KB Output is correct
17 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -