oj.uz

Submission #479199

# Submission time Handle Problem Language Result Execution time Memory
479199 2021-10-10T15:11:37 Z couplefire Fountain Parks (IOI21_parks) C++17
45 / 100
 1220 ms 48208 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second

int n, m;
vector<pii> pts, sqrs;
map<pii, int> pid, sid;
vector<int> fa, u_ans, v_ans, a_ans, b_ans;
vector<vector<pair<int, pii>>> adj;
vector<bool> vis;
set<pii> roads;

int find(int v){return v==fa[v]?v:fa[v]=find(fa[v]);}

void unite(int u, int v){
    u = find(u), v = find(v);
    if(u==v) return;
    fa[u] = v;
}

pii get(pii a, pii b){
    if(a.f==b.f){
        if(a.s>b.s) swap(a, b);
        int x = pid[{a.f-1, a.s+1}], y = pid[{a.f+1, a.s+1}];
        if(x>y) swap(x, y);
        return {x, y};
    }
    if(a.f>b.f) swap(a, b);
    int x = pid[{a.f+1, a.s+1}], y = pid[{a.f+1, a.s-1}];
    if(x>y) swap(x, y);
    return {x, y};
}

bool horz(pii a){
    return ((a.f+a.s)/2)&1;
}

void dfs(int v){
    vis[v] = 1;
    for(auto u : adj[v])
        if(!vis[u.f]) roads.erase(u.s), dfs(u.f);
}

int construct_roads(vector<int> _x, vector<int> _y){
    n = _x.size();
    for(int i = 0; i<n; ++i)
        pts.push_back({_x[i], _y[i]}), pid[pts.back()] = i;
    fa.resize(n);
    iota(fa.begin(), fa.end(), 0);
    for(int i = 0; i<n; ++i){
        pii npt = {pts[i].f+2, pts[i].s};
        if(pid.count(npt)) unite(i, pid[npt]);
        npt = {pts[i].f, pts[i].s+2};
        if(pid.count(npt)) unite(i, pid[npt]);       
    }
    for(int i = 1; i<n; ++i)
        if(find(0)!=find(i)) return 0;
    for(int i = 0; i<n; ++i){
        pii ap = {pts[i].f+2, pts[i].s}, bp = {pts[i].f, pts[i].s+2};
        if(pid.count(ap)) roads.insert({min(i, pid[ap]), max(i, pid[ap])});
        if(pid.count(bp)) roads.insert({min(i, pid[bp]), max(i, pid[bp])});
    }
    for(int i = 0; i<n; ++i){
        pii bl = pts[i], br = {bl.f+2, bl.s}, tl = {bl.f, bl.s+2}, tr = {bl.f+2, bl.s+2};
        if(pid.count(bl) && pid.count(br) && pid.count(tl) && pid.count(tr))
            sqrs.push_back({bl.f+1, bl.s+1}), sid[sqrs.back()] = (int)sqrs.size()-1;
    }
    m = (int)sqrs.size();
    adj.resize(m+1);
    vis.assign(m+1, 0);
    for(int i = 0; i<m; ++i){
        pii as, bs;
        if(horz(sqrs[i]))
            as = {sqrs[i].f+2, sqrs[i].s}, bs = {sqrs[i].f-2, sqrs[i].s};
        else as = {sqrs[i].f, sqrs[i].s+2}, bs = {sqrs[i].f, sqrs[i].s-2};
        if(sid.count(as)) adj[i].push_back({sid[as], get(sqrs[i], as)});
        if(sid.count(bs)) adj[i].push_back({sid[bs], get(sqrs[i], bs)});
        pii cs, ds;
        if(((sqrs[i].f+sqrs[i].s)/2)&1)
            cs = {sqrs[i].f, sqrs[i].s+2}, ds = {sqrs[i].f, sqrs[i].s-2};
        else cs = {sqrs[i].f+2, sqrs[i].s}, ds = {sqrs[i].f-2, sqrs[i].s};
        if(!sid.count(cs)) adj[m].push_back({i, get(sqrs[i], cs)});
        if(!sid.count(ds)) adj[m].push_back({i, get(sqrs[i], ds)});
    } dfs(m);
    for(auto [x, y] : roads){
        u_ans.push_back(x), v_ans.push_back(y);
        pii a = pts[x], b = pts[y];
        if(a.f==b.f){
            if(a.s>b.s) swap(a, b);
            if(horz({a.f-1, a.s+1})) a_ans.push_back(a.f-1), b_ans.push_back(a.s+1);
            else a_ans.push_back(a.f+1), b_ans.push_back({a.s+1});
        } else{
            if(a.f>b.f) swap(a, b);
            if(!horz({a.f+1, a.s-1})) a_ans.push_back(a.f+1), b_ans.push_back(a.s-1);
            else a_ans.push_back(a.f+1), b_ans.push_back(a.s+1);
        }
    }
    build(u_ans, v_ans, a_ans, b_ans);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 298 ms 21124 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 106 ms 12040 KB Output is correct
12 Correct 27 ms 3612 KB Output is correct
13 Correct 34 ms 5028 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 396 KB Output is correct
16 Correct 290 ms 21048 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 298 ms 21124 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 106 ms 12040 KB Output is correct
12 Correct 27 ms 3612 KB Output is correct
13 Correct 34 ms 5028 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 396 KB Output is correct
16 Correct 290 ms 21048 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 298 ms 21124 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 106 ms 12040 KB Output is correct
12 Correct 27 ms 3612 KB Output is correct
13 Correct 34 ms 5028 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 396 KB Output is correct
16 Correct 290 ms 21048 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 298 ms 21124 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 106 ms 12040 KB Output is correct
12 Correct 27 ms 3612 KB Output is correct
13 Correct 34 ms 5028 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 396 KB Output is correct
16 Correct 290 ms 21048 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Correct 0 ms 204 KB Output is correct
20 Correct 1022 ms 43964 KB Output is correct
21 Correct 972 ms 43612 KB Output is correct
22 Correct 987 ms 43536 KB Output is correct
23 Correct 727 ms 36960 KB Output is correct
24 Correct 344 ms 20012 KB Output is correct
25 Correct 415 ms 19880 KB Output is correct
26 Correct 373 ms 19812 KB Output is correct
27 Correct 916 ms 41984 KB Output is correct
28 Correct 958 ms 42152 KB Output is correct
29 Correct 1084 ms 42048 KB Output is correct
30 Correct 1111 ms 42112 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 40 ms 3412 KB Output is correct
33 Correct 121 ms 10652 KB Output is correct
34 Correct 889 ms 43928 KB Output is correct
35 Correct 10 ms 1336 KB Output is correct
36 Correct 61 ms 5404 KB Output is correct
37 Correct 145 ms 10528 KB Output is correct
38 Correct 323 ms 18068 KB Output is correct
39 Correct 472 ms 24020 KB Output is correct
40 Correct 661 ms 31712 KB Output is correct
41 Correct 865 ms 37824 KB Output is correct
42 Correct 1144 ms 43908 KB Output is correct
43 Correct 1 ms 204 KB Output is correct
44 Correct 1 ms 204 KB Output is correct
45 Correct 1 ms 204 KB Output is correct
46 Correct 0 ms 204 KB Output is correct
47 Correct 0 ms 204 KB Output is correct
48 Correct 1 ms 204 KB Output is correct
49 Correct 0 ms 204 KB Output is correct
50 Correct 1 ms 292 KB Output is correct
51 Correct 1 ms 204 KB Output is correct
52 Correct 1 ms 204 KB Output is correct
53 Correct 1 ms 204 KB Output is correct
54 Correct 2 ms 460 KB Output is correct
55 Correct 2 ms 588 KB Output is correct
56 Correct 375 ms 21140 KB Output is correct
57 Correct 622 ms 31504 KB Output is correct
58 Correct 611 ms 31432 KB Output is correct
59 Correct 1 ms 204 KB Output is correct
60 Correct 1 ms 204 KB Output is correct
61 Correct 1 ms 204 KB Output is correct
62 Correct 775 ms 42100 KB Output is correct
63 Correct 789 ms 42116 KB Output is correct
64 Correct 783 ms 41964 KB Output is correct
65 Correct 3 ms 588 KB Output is correct
66 Correct 7 ms 1072 KB Output is correct
67 Correct 353 ms 20968 KB Output is correct
68 Correct 634 ms 32444 KB Output is correct
69 Correct 1039 ms 42196 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 298 ms 21124 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 106 ms 12040 KB Output is correct
12 Correct 27 ms 3612 KB Output is correct
13 Correct 34 ms 5028 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 396 KB Output is correct
16 Correct 290 ms 21048 KB Output is correct
17 Correct 849 ms 42928 KB Output is correct
18 Correct 858 ms 43224 KB Output is correct
19 Correct 1002 ms 43412 KB Output is correct
20 Correct 1220 ms 47920 KB Output is correct
21 Correct 939 ms 39416 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 102 ms 7476 KB Output is correct
24 Correct 22 ms 2352 KB Output is correct
25 Correct 119 ms 7608 KB Output is correct
26 Correct 196 ms 12580 KB Output is correct
27 Correct 440 ms 24104 KB Output is correct
28 Correct 603 ms 29484 KB Output is correct
29 Correct 823 ms 37340 KB Output is correct
30 Correct 1022 ms 42232 KB Output is correct
31 Correct 1207 ms 48208 KB Output is correct
32 Correct 1049 ms 46264 KB Output is correct
33 Correct 760 ms 42128 KB Output is correct
34 Correct 5 ms 716 KB Output is correct
35 Correct 8 ms 1204 KB Output is correct
36 Correct 381 ms 22044 KB Output is correct
37 Correct 690 ms 34072 KB Output is correct
38 Correct 1029 ms 44412 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 292 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 288 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 298 ms 21124 KB Output is correct
10 Correct 17 ms 2508 KB Output is correct
11 Correct 106 ms 12040 KB Output is correct
12 Correct 27 ms 3612 KB Output is correct
13 Correct 34 ms 5028 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 2 ms 396 KB Output is correct
16 Correct 290 ms 21048 KB Output is correct
17 Incorrect 1 ms 204 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -