oj.uz

Submission #828506

# Submission time Handle Problem Language Result Execution time Memory
828506 2023-08-17T10:36:45 Z Magikarp4000 Fountain Parks (IOI21_parks) C++17
15 / 100
 293 ms 67424 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 2e5+5;
int n;
UM<int,int> col[MAXN];
vector<PII> pts,bch;
vector<pair<PII,int>> rds;
vector<int> v[MAXN];
bool z[MAXN];

void add(int a, int b, int idx) {
    rds.PB({{a,b},idx});
    v[a].PB(b);
    v[b].PB(a);
}

void dfs(int s) {
    if (z[s]) return;
    z[s] = 1;
    FORX(u,v[s]) dfs(u);
}

bool cmp(const PII &a, const PII &b) {
    if (a.S == b.S) return a.F < b.F;
    return a.S < b.S;
}

int construct_roads(std::vector<int> X, std::vector<int> Y) {
    n = X.size();
    FOR(i,0,n) pts.PB({X[i],Y[i]});
    FOR(i,0,n) col[X[i]][Y[i]] = i;
    int idx = 0;
    FOR(i,0,n) {
        int x = pts[i].F, y = pts[i].S;        
        if (col[x].count(y+2)) add(i,col[x][y+2],idx++);
        if (col[x+2].count(y)) add(i,col[x+2][y],idx++);
    }
    dfs(0);
    FOR(i,0,n) if (!z[i]) return 0;
    int m = rds.size();
    bch.resize(m);
    FORX(u,rds) {
        int x1 = pts[u.F.F].F, y1 = pts[u.F.F].S, x2 = pts[u.F.S].F, y2 = pts[u.F.S].S, idx = u.S;
        if (x1 == x2) {
            if (x1 == 2) bch[idx] = {1,(y1+y2)/2};
            else bch[idx] = {5,(y1+y2)/2};
        }
        else {
            bch[idx] = {(x1+x2)/2, y1-1};
        }
    }
    vector<int> ru,rv,ra,rb;
    FORX(u,rds) ru.PB(u.F.F), rv.PB(u.F.S);
    FORX(u,bch) ra.PB(u.F), rb.PB(u.S);
    build(ru,rv,ra,rb);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 8 ms 15960 KB Output is correct
8 Correct 8 ms 15964 KB Output is correct
9 Correct 90 ms 37236 KB Output is correct
10 Correct 14 ms 18004 KB Output is correct
11 Correct 38 ms 27252 KB Output is correct
12 Correct 16 ms 19140 KB Output is correct
13 Correct 20 ms 22012 KB Output is correct
14 Correct 9 ms 16084 KB Output is correct
15 Correct 9 ms 16084 KB Output is correct
16 Correct 80 ms 36424 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 8 ms 15960 KB Output is correct
8 Correct 8 ms 15964 KB Output is correct
9 Correct 90 ms 37236 KB Output is correct
10 Correct 14 ms 18004 KB Output is correct
11 Correct 38 ms 27252 KB Output is correct
12 Correct 16 ms 19140 KB Output is correct
13 Correct 20 ms 22012 KB Output is correct
14 Correct 9 ms 16084 KB Output is correct
15 Correct 9 ms 16084 KB Output is correct
16 Correct 80 ms 36424 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 8 ms 15964 KB Output is correct
19 Correct 9 ms 15956 KB Output is correct
20 Correct 10 ms 15956 KB Output is correct
21 Correct 8 ms 15944 KB Output is correct
22 Correct 10 ms 15956 KB Output is correct
23 Correct 245 ms 67424 KB Output is correct
24 Correct 8 ms 15964 KB Output is correct
25 Correct 11 ms 16220 KB Output is correct
26 Correct 9 ms 16340 KB Output is correct
27 Correct 9 ms 16404 KB Output is correct
28 Correct 83 ms 35624 KB Output is correct
29 Correct 126 ms 46748 KB Output is correct
30 Correct 185 ms 56284 KB Output is correct
31 Correct 272 ms 67364 KB Output is correct
32 Correct 10 ms 15956 KB Output is correct
33 Correct 8 ms 15956 KB Output is correct
34 Correct 9 ms 15956 KB Output is correct
35 Correct 8 ms 15960 KB Output is correct
36 Correct 8 ms 15956 KB Output is correct
37 Correct 9 ms 15956 KB Output is correct
38 Correct 8 ms 15956 KB Output is correct
39 Correct 8 ms 15912 KB Output is correct
40 Correct 8 ms 15932 KB Output is correct
41 Correct 8 ms 15956 KB Output is correct
42 Correct 8 ms 15936 KB Output is correct
43 Correct 9 ms 16084 KB Output is correct
44 Correct 10 ms 16232 KB Output is correct
45 Correct 84 ms 36652 KB Output is correct
46 Correct 136 ms 45008 KB Output is correct
47 Correct 134 ms 44800 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 8 ms 15960 KB Output is correct
8 Correct 8 ms 15964 KB Output is correct
9 Correct 90 ms 37236 KB Output is correct
10 Correct 14 ms 18004 KB Output is correct
11 Correct 38 ms 27252 KB Output is correct
12 Correct 16 ms 19140 KB Output is correct
13 Correct 20 ms 22012 KB Output is correct
14 Correct 9 ms 16084 KB Output is correct
15 Correct 9 ms 16084 KB Output is correct
16 Correct 80 ms 36424 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 8 ms 15964 KB Output is correct
19 Correct 9 ms 15956 KB Output is correct
20 Correct 10 ms 15956 KB Output is correct
21 Correct 8 ms 15944 KB Output is correct
22 Correct 10 ms 15956 KB Output is correct
23 Correct 245 ms 67424 KB Output is correct
24 Correct 8 ms 15964 KB Output is correct
25 Correct 11 ms 16220 KB Output is correct
26 Correct 9 ms 16340 KB Output is correct
27 Correct 9 ms 16404 KB Output is correct
28 Correct 83 ms 35624 KB Output is correct
29 Correct 126 ms 46748 KB Output is correct
30 Correct 185 ms 56284 KB Output is correct
31 Correct 272 ms 67364 KB Output is correct
32 Correct 10 ms 15956 KB Output is correct
33 Correct 8 ms 15956 KB Output is correct
34 Correct 9 ms 15956 KB Output is correct
35 Correct 8 ms 15960 KB Output is correct
36 Correct 8 ms 15956 KB Output is correct
37 Correct 9 ms 15956 KB Output is correct
38 Correct 8 ms 15956 KB Output is correct
39 Correct 8 ms 15912 KB Output is correct
40 Correct 8 ms 15932 KB Output is correct
41 Correct 8 ms 15956 KB Output is correct
42 Correct 8 ms 15936 KB Output is correct
43 Correct 9 ms 16084 KB Output is correct
44 Correct 10 ms 16232 KB Output is correct
45 Correct 84 ms 36652 KB Output is correct
46 Correct 136 ms 45008 KB Output is correct
47 Correct 134 ms 44800 KB Output is correct
48 Incorrect 9 ms 15964 KB Tree @(5, 3) appears more than once: for edges on positions 0 and 1
49 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 8 ms 15960 KB Output is correct
8 Correct 8 ms 15964 KB Output is correct
9 Correct 90 ms 37236 KB Output is correct
10 Correct 14 ms 18004 KB Output is correct
11 Correct 38 ms 27252 KB Output is correct
12 Correct 16 ms 19140 KB Output is correct
13 Correct 20 ms 22012 KB Output is correct
14 Correct 9 ms 16084 KB Output is correct
15 Correct 9 ms 16084 KB Output is correct
16 Correct 80 ms 36424 KB Output is correct
17 Incorrect 9 ms 15956 KB Tree (a[0], b[0]) = (5, 3) is not adjacent to edge between u[0]=0 @(200000, 2) and v[0]=1 @(200000, 4)
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 8 ms 15960 KB Output is correct
8 Correct 8 ms 15964 KB Output is correct
9 Correct 90 ms 37236 KB Output is correct
10 Correct 14 ms 18004 KB Output is correct
11 Correct 38 ms 27252 KB Output is correct
12 Correct 16 ms 19140 KB Output is correct
13 Correct 20 ms 22012 KB Output is correct
14 Correct 9 ms 16084 KB Output is correct
15 Correct 9 ms 16084 KB Output is correct
16 Correct 80 ms 36424 KB Output is correct
17 Incorrect 293 ms 63296 KB Tree (a[1], b[1]) = (5, 52499) is not adjacent to edge between u[1]=1 @(100002, 52498) and v[1]=117727 @(100002, 52500)
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 15956 KB Output is correct
2 Correct 7 ms 15956 KB Output is correct
3 Correct 7 ms 15956 KB Output is correct
4 Correct 8 ms 15956 KB Output is correct
5 Correct 7 ms 15956 KB Output is correct
6 Correct 7 ms 15956 KB Output is correct
7 Correct 8 ms 15960 KB Output is correct
8 Correct 8 ms 15964 KB Output is correct
9 Correct 90 ms 37236 KB Output is correct
10 Correct 14 ms 18004 KB Output is correct
11 Correct 38 ms 27252 KB Output is correct
12 Correct 16 ms 19140 KB Output is correct
13 Correct 20 ms 22012 KB Output is correct
14 Correct 9 ms 16084 KB Output is correct
15 Correct 9 ms 16084 KB Output is correct
16 Correct 80 ms 36424 KB Output is correct
17 Correct 7 ms 15956 KB Output is correct
18 Correct 8 ms 15964 KB Output is correct
19 Correct 9 ms 15956 KB Output is correct
20 Correct 10 ms 15956 KB Output is correct
21 Correct 8 ms 15944 KB Output is correct
22 Correct 10 ms 15956 KB Output is correct
23 Correct 245 ms 67424 KB Output is correct
24 Correct 8 ms 15964 KB Output is correct
25 Correct 11 ms 16220 KB Output is correct
26 Correct 9 ms 16340 KB Output is correct
27 Correct 9 ms 16404 KB Output is correct
28 Correct 83 ms 35624 KB Output is correct
29 Correct 126 ms 46748 KB Output is correct
30 Correct 185 ms 56284 KB Output is correct
31 Correct 272 ms 67364 KB Output is correct
32 Correct 10 ms 15956 KB Output is correct
33 Correct 8 ms 15956 KB Output is correct
34 Correct 9 ms 15956 KB Output is correct
35 Correct 8 ms 15960 KB Output is correct
36 Correct 8 ms 15956 KB Output is correct
37 Correct 9 ms 15956 KB Output is correct
38 Correct 8 ms 15956 KB Output is correct
39 Correct 8 ms 15912 KB Output is correct
40 Correct 8 ms 15932 KB Output is correct
41 Correct 8 ms 15956 KB Output is correct
42 Correct 8 ms 15936 KB Output is correct
43 Correct 9 ms 16084 KB Output is correct
44 Correct 10 ms 16232 KB Output is correct
45 Correct 84 ms 36652 KB Output is correct
46 Correct 136 ms 45008 KB Output is correct
47 Correct 134 ms 44800 KB Output is correct
48 Incorrect 9 ms 15964 KB Tree @(5, 3) appears more than once: for edges on positions 0 and 1
49 Halted 0 ms 0 KB -