oj.uz

Submission #439828

# Submission time Handle Problem Language Result Execution time Memory
439828 2021-06-30T23:22:28 Z humbertoyusta Fountain Parks (IOI21_parks) C++17
45 / 100
 791 ms 90344 KB 
#include "parks.h"
#include<bits/stdc++.h>
#define f first
#define s second
#define ii pair<int,int>
using namespace std;
#define maxn 200010
#define db(x) cerr<<#x<<": "<<(x)<<"\n";

int mx[4] = { 0 , 2 , 0 , -2 };
int my[4] = { 2 , 0 , -2 , 0 };
int vis[maxn];
ii arr[maxn];
map<ii,int> mk;
vector<int> U, V, A, B;
map<ii,int> mp;

bool add_edge(int u,int v,int plus_){
    U.push_back(u);
    V.push_back(v);
    if( arr[u].f != arr[v].f ){
        if( mk[{(arr[u].f+arr[v].f)/2,arr[u].s + plus_}] ) return false;
        A.push_back( (arr[u].f+arr[v].f)/2 );
        B.push_back( arr[u].s + plus_ );
        mk[{(arr[u].f+arr[v].f)/2,arr[u].s + plus_}] = true;
    }
    else{
        if( mk[{arr[u].f + plus_,(arr[u].s+arr[v].s)/2}] ) return false;
        A.push_back( arr[u].f + plus_ );
        B.push_back( (arr[u].s+arr[v].s)/2 );
        mk[{arr[u].f + plus_,(arr[u].s+arr[v].s)/2}] = true;
    }
    return true;
}

void dfs(int u,int p,int plus_){
    vis[u] = 1;
    for(int i=0; i<4; i++){
        int nx = arr[u].f + mx[i];
        int ny = arr[u].s + my[i];
        if( mp[{nx,ny}] ){
            int v = mp[{nx,ny}] - 1;
            if( vis[v] ) continue;

            int gp = p / 2 * 2 + ( p + 1 ) % 2;
            int nplus = plus_;
            if( i != gp ) nplus *= -1;

            if( add_edge(u,v,nplus) )
                dfs(v,i,nplus);
        }
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
//    if (x.size() == 1) {
//        vector<int> pra;
//        build(pra, pra, pra, pra);
//        return 1;
//    }

    int n = x.size();

    pair<ii,int> st = { { 2000000007 , 2000000007 } , -1 };
    for(int i=0; i<n; i++){
        arr[i] = {x[i],y[i]};
        mp[{x[i],y[i]}] = i + 1;
        st = min( st , { arr[i] , i } );
    }

    int u = st.s;
    vis[u] = 1;
    for(int i=0; i<4; i++){
        int nx = arr[u].f + mx[i];
        int ny = arr[u].s + my[i];
        if( mp[{nx,ny}] ){
            int v = mp[{nx,ny}] - 1;
            if( vis[v] ) continue;
            int plus_ = ( i == 1 ) + ( i == 2 ) - ( i == 0 ) - ( i == 3 );
            add_edge(u,v,plus_);
            dfs(v,i,plus_);
        }
    }

    for(int i=0; i<n; i++)
        if( vis[i] == 0 )
            return 0;

    build(U, V, A, B);
    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 204 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 296 ms 45284 KB Output is correct
10 Correct 21 ms 4996 KB Output is correct
11 Correct 134 ms 24516 KB Output is correct
12 Correct 33 ms 7280 KB Output is correct
13 Correct 68 ms 14148 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 45224 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 204 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 296 ms 45284 KB Output is correct
10 Correct 21 ms 4996 KB Output is correct
11 Correct 134 ms 24516 KB Output is correct
12 Correct 33 ms 7280 KB Output is correct
13 Correct 68 ms 14148 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 45224 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Incorrect 1 ms 204 KB Wrong answer detected in grader
20 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 204 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 296 ms 45284 KB Output is correct
10 Correct 21 ms 4996 KB Output is correct
11 Correct 134 ms 24516 KB Output is correct
12 Correct 33 ms 7280 KB Output is correct
13 Correct 68 ms 14148 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 45224 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Incorrect 1 ms 204 KB Wrong answer detected in grader
20 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 204 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 296 ms 45284 KB Output is correct
10 Correct 21 ms 4996 KB Output is correct
11 Correct 134 ms 24516 KB Output is correct
12 Correct 33 ms 7280 KB Output is correct
13 Correct 68 ms 14148 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 45224 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 583 ms 78220 KB Output is correct
21 Correct 594 ms 65612 KB Output is correct
22 Correct 605 ms 78020 KB Output is correct
23 Correct 526 ms 71860 KB Output is correct
24 Correct 164 ms 17472 KB Output is correct
25 Correct 185 ms 18260 KB Output is correct
26 Correct 165 ms 18384 KB Output is correct
27 Correct 502 ms 52884 KB Output is correct
28 Correct 518 ms 53156 KB Output is correct
29 Correct 628 ms 52880 KB Output is correct
30 Correct 791 ms 52948 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 31 ms 5068 KB Output is correct
33 Correct 77 ms 8900 KB Output is correct
34 Correct 579 ms 78352 KB Output is correct
35 Correct 12 ms 1868 KB Output is correct
36 Correct 45 ms 6140 KB Output is correct
37 Correct 88 ms 10560 KB Output is correct
38 Correct 200 ms 19872 KB Output is correct
39 Correct 315 ms 27144 KB Output is correct
40 Correct 397 ms 34544 KB Output is correct
41 Correct 503 ms 41880 KB Output is correct
42 Correct 593 ms 49280 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 1 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 1 ms 204 KB Output is correct
50 Correct 1 ms 204 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 716 KB Output is correct
55 Correct 3 ms 716 KB Output is correct
56 Correct 293 ms 38812 KB Output is correct
57 Correct 460 ms 56180 KB Output is correct
58 Correct 448 ms 56168 KB Output is correct
59 Correct 1 ms 204 KB Output is correct
60 Correct 1 ms 204 KB Output is correct
61 Correct 0 ms 204 KB Output is correct
62 Correct 636 ms 84008 KB Output is correct
63 Correct 654 ms 71548 KB Output is correct
64 Correct 648 ms 77388 KB Output is correct
65 Correct 4 ms 1100 KB Output is correct
66 Correct 9 ms 1356 KB Output is correct
67 Correct 275 ms 34872 KB Output is correct
68 Correct 467 ms 52412 KB Output is correct
69 Correct 686 ms 69756 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 204 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 296 ms 45284 KB Output is correct
10 Correct 21 ms 4996 KB Output is correct
11 Correct 134 ms 24516 KB Output is correct
12 Correct 33 ms 7280 KB Output is correct
13 Correct 68 ms 14148 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 45224 KB Output is correct
17 Correct 668 ms 90344 KB Output is correct
18 Correct 619 ms 84176 KB Output is correct
19 Correct 603 ms 78052 KB Output is correct
20 Correct 596 ms 60116 KB Output is correct
21 Correct 533 ms 62216 KB Output is correct
22 Correct 1 ms 204 KB Output is correct
23 Correct 80 ms 9600 KB Output is correct
24 Correct 25 ms 3792 KB Output is correct
25 Correct 61 ms 8600 KB Output is correct
26 Correct 112 ms 13252 KB Output is correct
27 Correct 269 ms 30840 KB Output is correct
28 Correct 338 ms 38688 KB Output is correct
29 Correct 420 ms 46336 KB Output is correct
30 Correct 526 ms 53816 KB Output is correct
31 Correct 615 ms 61656 KB Output is correct
32 Correct 576 ms 72728 KB Output is correct
33 Correct 606 ms 84124 KB Output is correct
34 Correct 6 ms 1228 KB Output is correct
35 Correct 7 ms 1484 KB Output is correct
36 Correct 306 ms 33624 KB Output is correct
37 Correct 420 ms 50136 KB Output is correct
38 Correct 600 ms 66840 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 204 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 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 296 ms 45284 KB Output is correct
10 Correct 21 ms 4996 KB Output is correct
11 Correct 134 ms 24516 KB Output is correct
12 Correct 33 ms 7280 KB Output is correct
13 Correct 68 ms 14148 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 2 ms 588 KB Output is correct
16 Correct 296 ms 45224 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 0 ms 204 KB Output is correct
19 Incorrect 1 ms 204 KB Wrong answer detected in grader
20 Halted 0 ms 0 KB -