oj.uz

Submission #838477

# Submission time Handle Problem Language Result Execution time Memory
838477 2023-08-27T07:31:07 Z fatemetmhr Fountain Parks (IOI21_parks) C++17
5 / 100
 841 ms 73632 KB 
// Be Name Khoda //
 
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,O3")
 
#include "parks.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
#define debug(x)  cerr << "(" << (#x) << "): " << (x) << endl;
#define all(x)    x.begin(), x.end()
#define MAX(x, y) ((x) > (y) ? (x) : (y))
#define MIN(x, y) ((x) < (y) ? (x) : (y))
#define fi        first
#define se        second
#define pb        push_back
#define mp        make_pair
 
const int maxn5 = 1e6 + 10;
 
 
int n;
vector <int> ret[2], ed[2];
map <pair<int, int>, int> av, cnt, idof;
set <pair<pair<int, int>, pair<int, int>>> rem;


void dfs(int v, int x, int y){
    av.erase(mp(x, y));
    if(av.find(mp(x - 2, y)) != av.end()){
        int u = av[mp(x - 2, y)];
        dfs(u, x - 2, y);
    }
    if(av.find(mp(x + 2, y)) != av.end()){
        int u = av[mp(x + 2, y)];
        dfs(u, x + 2, y);
    }
    if(av.find(mp(x, y - 2)) != av.end()){
        int u = av[mp(x, y - 2)];
        dfs(u, x, y - 2);
    }
    if(av.find(mp(x, y + 2)) != av.end()){
        int u = av[mp(x, y + 2)];
        dfs(u, x, y + 2);
    }
}
 
 
int construct_roads(std::vector<int> x, std::vector<int> y) {

    n = x.size();

    for(int i = 0; i < n; i++)
        av[mp(x[i], y[i])] = i;
    dfs(0, x[0], y[0]);
    if(av.size())
        return 0;

    for(int i = 0; i < n; i++){
        cnt[mp(x[i] - 1, y[i] - 1)]++;
        cnt[mp(x[i] + 1, y[i] - 1)]++;
        cnt[mp(x[i] - 1, y[i] + 1)]++;
        cnt[mp(x[i] + 1, y[i] + 1)]++;
        idof[mp(x[i], y[i])] = i;
    }


    for(auto it = cnt.begin(); it != cnt.end(); it++) if(it -> se == 4){
        int x = (it -> fi).fi, y = (it -> fi).se;
        x--; y--;
        if(((x / 2) + (y / 2)) % 2){ // is black
            rem.insert({{x, y}, {x + 2, y}});
        }
        else{ // is white
            rem.insert({{x, y}, {x, y + 2}});
        }
    }

    for(int i = 0; i < n; i++){
        if(idof.find(mp(x[i] + 2, y[i])) != idof.end() &&
            rem.find(mp(mp(x[i], y[i]), mp(x[i] + 2, y[i]))) == rem.end()){
            ed[0].pb(i);
            ed[1].pb(idof[mp(x[i] + 2, y[i])]);
            ret[0].pb(x[i] + 1);
            if(((x[i] / 2) + (y[i] / 2)) % 2)
                ret[1].pb(y[i] + 1);
            else
                ret[1].pb(y[i] - 1);
        }

        if(idof.find(mp(x[i], y[i] + 2)) != idof.end() &&
            rem.find(mp(mp(x[i], y[i]), mp(x[i], y[i] + 2))) == rem.end()){
            ed[0].pb(i);
            ed[1].pb(idof[mp(x[i], y[i] + 2)]);
            ret[1].pb(y[i] + 1);
            if(((x[i] / 2) + (y[i] / 2)) % 2)
                ret[0].pb(x[i] + 1);
            else
                ret[0].pb(x[i] - 1);
        }
    }

    build(ed[0], ed[1], ret[0], ret[1]);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 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 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 296 ms 27460 KB Output is correct
10 Correct 14 ms 3028 KB Output is correct
11 Correct 100 ms 14276 KB Output is correct
12 Correct 23 ms 4396 KB Output is correct
13 Correct 21 ms 4008 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 268 ms 33460 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 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 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 296 ms 27460 KB Output is correct
10 Correct 14 ms 3028 KB Output is correct
11 Correct 100 ms 14276 KB Output is correct
12 Correct 23 ms 4396 KB Output is correct
13 Correct 21 ms 4008 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 268 ms 33460 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Incorrect 0 ms 212 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 1
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 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 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 296 ms 27460 KB Output is correct
10 Correct 14 ms 3028 KB Output is correct
11 Correct 100 ms 14276 KB Output is correct
12 Correct 23 ms 4396 KB Output is correct
13 Correct 21 ms 4008 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 268 ms 33460 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Incorrect 0 ms 212 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 1
19 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 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 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 296 ms 27460 KB Output is correct
10 Correct 14 ms 3028 KB Output is correct
11 Correct 100 ms 14276 KB Output is correct
12 Correct 23 ms 4396 KB Output is correct
13 Correct 21 ms 4008 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 268 ms 33460 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 Incorrect 841 ms 67524 KB Tree @(192371, 7633) appears more than once: for edges on positions 0 and 1
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 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 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 296 ms 27460 KB Output is correct
10 Correct 14 ms 3028 KB Output is correct
11 Correct 100 ms 14276 KB Output is correct
12 Correct 23 ms 4396 KB Output is correct
13 Correct 21 ms 4008 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 268 ms 33460 KB Output is correct
17 Incorrect 836 ms 73632 KB Tree @(100001, 3) appears more than once: for edges on positions 31819 and 138412
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 304 KB Output is correct
3 Correct 1 ms 212 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 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 296 ms 27460 KB Output is correct
10 Correct 14 ms 3028 KB Output is correct
11 Correct 100 ms 14276 KB Output is correct
12 Correct 23 ms 4396 KB Output is correct
13 Correct 21 ms 4008 KB Output is correct
14 Correct 1 ms 300 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 268 ms 33460 KB Output is correct
17 Correct 1 ms 300 KB Output is correct
18 Incorrect 0 ms 212 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 1
19 Halted 0 ms 0 KB -