oj.uz

Submission #602979

# Submission time Handle Problem Language Result Execution time Memory
602979 2022-07-23T13:38:08 Z 2fat2code Fountain Parks (IOI21_parks) C++17
5 / 100
 373 ms 47424 KB 
#include "parks.h"
#include <bits/stdc++.h>
#define fr first
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#define sc second
#define all(s) s.begin(), s.end()
//#define int long long
#define rc(s) return cout << s, 0
using namespace std;

const int nmax = 200005;

int n, par[nmax];
vector<pair<int,int>>vertex;
map <pair<int,int>, int>varfuri, banci;
vector<int>u, v, assigned_a, assigned_b;

int findpar(int x){
    if(x != par[x]){
        par[x] = findpar(par[x]);
    }
    return par[x];
}

void join(int x, int y){
    x = findpar(x);
    y = findpar(y);
    par[x] = y;
}

int construct_roads(vector<int> x, vector<int> y) {
    n = (int)x.size();
    for(int i=0;i<n;i++){
        vertex.push_back({x[i], y[i]});
        varfuri[{x[i], y[i]}] = i;
    }
    sort(all(vertex));
    for(auto it : vertex){
        if(varfuri.count({it.fr - 2, it.sc})){
            if(it.fr % 4 == 0){
                if(it.sc % 4 == 2){
                    if(!banci.count({it.fr - 1, it.sc - 1})){
                        banci[{it.fr-1, it.sc-1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr - 2, it.sc}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
                else{
                    if(!banci.count({it.fr - 1, it.sc + 1})){
                        banci[{it.fr-1, it.sc + 1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr - 2, it.sc}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc + 1);
                    }
                }
            }
            else{
                if(it.sc % 4 == 2){
                    if(!banci.count({it.fr - 1, it.sc + 1})){
                        banci[{it.fr-1, it.sc+1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr - 2, it.sc}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc + 1);
                    }
                }
                else{
                    if(!banci.count({it.fr - 1, it.sc - 1})){
                        banci[{it.fr-1, it.sc-1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr - 2, it.sc}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
            }
        }
        if(varfuri.count({it.fr, it.sc - 2})){
            if(it.fr % 4 == 0){
                if(it.sc % 4 == 2){
                    if(!banci.count({it.fr - 1, it.sc + 1})){
                        banci[{it.fr-1, it.sc+1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr, it.sc - 2}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc + 1);
                    }
                }
                else{
                    if(!banci.count({it.fr - 1, it.sc - 1})){
                        banci[{it.fr-1, it.sc - 1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr, it.sc - 2}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
            }
            else{
                if(it.sc % 4 == 2){
                    if(!banci.count({it.fr - 1, it.sc - 1})){
                        banci[{it.fr-1, it.sc-1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr, it.sc - 2}]);
                        assigned_a.push_back(it.fr - 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
                else{
                    if(!banci.count({it.fr + 1, it.sc - 1})){
                        banci[{it.fr+1, it.sc-1}] = 1;
                        u.push_back(varfuri[{it.fr, it.sc}]);
                        v.push_back(varfuri[{it.fr, it.sc - 2}]);
                        assigned_a.push_back(it.fr + 1);
                        assigned_b.push_back(it.sc - 1);
                    }
                }
            }
        }
    }
    for(int i=0;i<n;i++) par[i] = i;
    for(int i=0;i<(int)u.size();i++){
        join(u[i], v[i]);
    }
    for(int i=0;i<n;i++){
        findpar(i);
    }
    for(int i=0;i<n-1;i++){
        if(par[i] != par[i + 1]) return 0;
    }
    build(u, v, assigned_a, assigned_b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 159 ms 22436 KB Output is correct
10 Correct 15 ms 2496 KB Output is correct
11 Correct 73 ms 12120 KB Output is correct
12 Correct 18 ms 3664 KB Output is correct
13 Correct 48 ms 8180 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 161 ms 22400 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 159 ms 22436 KB Output is correct
10 Correct 15 ms 2496 KB Output is correct
11 Correct 73 ms 12120 KB Output is correct
12 Correct 18 ms 3664 KB Output is correct
13 Correct 48 ms 8180 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 161 ms 22400 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Incorrect 1 ms 212 KB Tree (a[2], b[2]) = (3, 7) is not adjacent to edge between u[2]=3 @(4, 6) and v[2]=0 @(4, 4)
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 159 ms 22436 KB Output is correct
10 Correct 15 ms 2496 KB Output is correct
11 Correct 73 ms 12120 KB Output is correct
12 Correct 18 ms 3664 KB Output is correct
13 Correct 48 ms 8180 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 161 ms 22400 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Incorrect 1 ms 212 KB Tree (a[2], b[2]) = (3, 7) is not adjacent to edge between u[2]=3 @(4, 6) and v[2]=0 @(4, 4)
19 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 159 ms 22436 KB Output is correct
10 Correct 15 ms 2496 KB Output is correct
11 Correct 73 ms 12120 KB Output is correct
12 Correct 18 ms 3664 KB Output is correct
13 Correct 48 ms 8180 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 161 ms 22400 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 363 ms 47424 KB Output is correct
21 Incorrect 307 ms 36536 KB Solution announced impossible, but it is possible.
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 159 ms 22436 KB Output is correct
10 Correct 15 ms 2496 KB Output is correct
11 Correct 73 ms 12120 KB Output is correct
12 Correct 18 ms 3664 KB Output is correct
13 Correct 48 ms 8180 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 161 ms 22400 KB Output is correct
17 Correct 372 ms 45624 KB Output is correct
18 Correct 373 ms 45880 KB Output is correct
19 Incorrect 311 ms 35976 KB Solution announced impossible, but it is possible.
20 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 316 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 159 ms 22436 KB Output is correct
10 Correct 15 ms 2496 KB Output is correct
11 Correct 73 ms 12120 KB Output is correct
12 Correct 18 ms 3664 KB Output is correct
13 Correct 48 ms 8180 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 161 ms 22400 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Incorrect 1 ms 212 KB Tree (a[2], b[2]) = (3, 7) is not adjacent to edge between u[2]=3 @(4, 6) and v[2]=0 @(4, 4)
19 Halted 0 ms 0 KB -