oj.uz

Submission #828893

# Submission time Handle Problem Language Result Execution time Memory
828893 2023-08-17T18:41:38 Z fatemetmhr Fountain Parks (IOI21_parks) C++17
5 / 100
 271 ms 63400 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, q[maxn5], cnt[maxn5];
pair <int, pair<int, int>> qq[maxn5];
bool mark[maxn5];
vector <int> ret[2], ed[2], edg[maxn5];
vector <pair<int, int>> ver;
pair<pair <int, int>, pair<int, int>> adj[maxn5];
map <pair<int, int>, int> av;
 
void bfs(int v, int x, int y){
    int l = 0, r = 1;
    av.erase(mp(x, y));
    qq[0] = {v, {x, y}};
    while(l < r){
        int v = qq[l].fi, x = qq[l].se.fi, y = qq[l].se.se;
        l++;
        if(av.find(mp(x - 2, y)) != av.end()){
            int u = av[mp(x - 2, y)];
            ed[0].pb(v);
            ed[1].pb(u);
            av.erase(mp(x - 2, y));
            qq[r++] = {u, {x - 2, y}};
        }
        if(av.find(mp(x + 2, y)) != av.end()){
            int u = av[mp(x + 2, y)];
            ed[0].pb(v);
            ed[1].pb(u);
            av.erase(mp(x + 2, y));
            qq[r++] = {u, {x + 1, y}};
        }
        if(av.find(mp(x, y - 2)) != av.end()){
            int u = av[mp(x, y - 2)];
            ed[0].pb(v);
            ed[1].pb(u);
            av.erase(mp(x, y - 2));
            qq[r++] = {u, {x, y - 2}};
        }
        if(av.find(mp(x, y + 2)) != av.end()){
            int u = av[mp(x, y + 2)];
            ed[0].pb(v);
            ed[1].pb(u);
            av.erase(mp(x, y + 2));
            qq[r++] = {u, {x, y + 2}};
        }
    }
}
 
void dfs2(int v){
    mark[v] = true;
    for(auto u : edg[v]) if(!mark[u]){
        mark[u] = true;
        //debug(v);
        //debug(u);
        ret[0][v] = ver[u - (n - 1)].fi;
        ret[1][v] = ver[u - (n - 1)].se;
        for(auto z : edg[u]) if(!mark[z])
            dfs2(z);
        return;
    }
}
 
 
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;
    bfs(0, x[0], y[0]);
    if(av.size())
        return 0;
 
    for(int i = 0; i < n - 1; i++){
        if(x[ed[0][i]] == x[ed[1][i]]){
            adj[i].fi = mp(x[ed[0][i]] - 1, (y[ed[0][i]] + y[ed[1][i]]) / 2);
            adj[i].se = mp(x[ed[0][i]] + 1, (y[ed[0][i]] + y[ed[1][i]]) / 2);
        }
        else{
            adj[i].fi = mp((x[ed[0][i]] + x[ed[1][i]]) / 2, y[ed[0][i]] - 1);
            adj[i].se = mp((x[ed[0][i]] + x[ed[1][i]]) / 2, y[ed[0][i]] + 1);
        }
        ver.pb(adj[i].fi);
        ver.pb(adj[i].se);
    }
 
    sort(all(ver));
    ver.resize(unique(all(ver)) - ver.begin());
    for(int i = 0; i < n - 1; i++){
        int pt = lower_bound(all(ver), adj[i].fi) - ver.begin();
        edg[i].pb(pt + n - 1);
        pt = lower_bound(all(ver), adj[i].se) - ver.begin();
        edg[i].pb(pt + n - 1);
        edg[edg[i][0]].pb(i);
        edg[edg[i][1]].pb(i);
        cnt[edg[i][0]]++;
        cnt[edg[i][1]]++;
    }
    /*
    for(int i = 0; i < int(ver.size()) + n - 1; i++){
        //debug(i);
        for(auto u : edg[i])
            cout << u << ' ';
        cout << endl;
    }
    //*/
    int l = 0, r = 0;
    for(int i = 0; i < int(ver.size()); i++) if(edg[i + n - 1].size() == 1){
        q[r++] = i + n - 1;
        mark[i + n - 1] = true;
    }
    ret[0].resize(n - 1);
    ret[1].resize(n - 1);
    //debug(r);
    while(l < r){
        int v = q[l++];
        for(auto u : edg[v]) if(!mark[u]){
            mark[u] = true;
            for(auto z : edg[u]){
                cnt[z]--;
                if(!mark[z] && cnt[z] == 1){
                    q[r++] = z;
                    mark[z] = true;
                }
            }
            ret[0][u] = ver[v - (n - 1)].fi;
            ret[1][u] = ver[v - (n - 1)].se;
        }
    }
    //return 0;
    //cout << ed[0].size() << ' ' << ed[1].size() << ' ' << ret[0].size() << ' ' << ret[1].size() << endl;
    for(int i = 0; i < n - 1; i++) if(!mark[i])
        dfs2(i);
    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 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 11 ms 23796 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23736 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 11 ms 23768 KB Output is correct
9 Correct 133 ms 45632 KB Output is correct
10 Correct 21 ms 26196 KB Output is correct
11 Correct 74 ms 35748 KB Output is correct
12 Correct 26 ms 27348 KB Output is correct
13 Correct 40 ms 27572 KB Output is correct
14 Correct 11 ms 23892 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 136 ms 46072 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 11 ms 23796 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23736 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 11 ms 23768 KB Output is correct
9 Correct 133 ms 45632 KB Output is correct
10 Correct 21 ms 26196 KB Output is correct
11 Correct 74 ms 35748 KB Output is correct
12 Correct 26 ms 27348 KB Output is correct
13 Correct 40 ms 27572 KB Output is correct
14 Correct 11 ms 23892 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 136 ms 46072 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 11 ms 23764 KB Output is correct
19 Correct 11 ms 23708 KB Output is correct
20 Correct 11 ms 23764 KB Output is correct
21 Correct 12 ms 23764 KB Output is correct
22 Correct 11 ms 23764 KB Output is correct
23 Correct 271 ms 63400 KB Output is correct
24 Incorrect 11 ms 23764 KB Solution announced impossible, but it is possible.
25 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 11 ms 23796 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23736 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 11 ms 23768 KB Output is correct
9 Correct 133 ms 45632 KB Output is correct
10 Correct 21 ms 26196 KB Output is correct
11 Correct 74 ms 35748 KB Output is correct
12 Correct 26 ms 27348 KB Output is correct
13 Correct 40 ms 27572 KB Output is correct
14 Correct 11 ms 23892 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 136 ms 46072 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 11 ms 23764 KB Output is correct
19 Correct 11 ms 23708 KB Output is correct
20 Correct 11 ms 23764 KB Output is correct
21 Correct 12 ms 23764 KB Output is correct
22 Correct 11 ms 23764 KB Output is correct
23 Correct 271 ms 63400 KB Output is correct
24 Incorrect 11 ms 23764 KB Solution announced impossible, but it is possible.
25 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 11 ms 23796 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23736 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 11 ms 23768 KB Output is correct
9 Correct 133 ms 45632 KB Output is correct
10 Correct 21 ms 26196 KB Output is correct
11 Correct 74 ms 35748 KB Output is correct
12 Correct 26 ms 27348 KB Output is correct
13 Correct 40 ms 27572 KB Output is correct
14 Correct 11 ms 23892 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 136 ms 46072 KB Output is correct
17 Correct 12 ms 23764 KB Output is correct
18 Correct 11 ms 23760 KB Output is correct
19 Correct 10 ms 23764 KB Output is correct
20 Incorrect 149 ms 43384 KB Solution announced impossible, but it is possible.
21 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 11 ms 23796 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23736 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 11 ms 23768 KB Output is correct
9 Correct 133 ms 45632 KB Output is correct
10 Correct 21 ms 26196 KB Output is correct
11 Correct 74 ms 35748 KB Output is correct
12 Correct 26 ms 27348 KB Output is correct
13 Correct 40 ms 27572 KB Output is correct
14 Correct 11 ms 23892 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 136 ms 46072 KB Output is correct
17 Incorrect 141 ms 41444 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 11 ms 23764 KB Output is correct
3 Correct 13 ms 23764 KB Output is correct
4 Correct 11 ms 23796 KB Output is correct
5 Correct 11 ms 23764 KB Output is correct
6 Correct 11 ms 23736 KB Output is correct
7 Correct 13 ms 23764 KB Output is correct
8 Correct 11 ms 23768 KB Output is correct
9 Correct 133 ms 45632 KB Output is correct
10 Correct 21 ms 26196 KB Output is correct
11 Correct 74 ms 35748 KB Output is correct
12 Correct 26 ms 27348 KB Output is correct
13 Correct 40 ms 27572 KB Output is correct
14 Correct 11 ms 23892 KB Output is correct
15 Correct 12 ms 23892 KB Output is correct
16 Correct 136 ms 46072 KB Output is correct
17 Correct 11 ms 23764 KB Output is correct
18 Correct 11 ms 23764 KB Output is correct
19 Correct 11 ms 23708 KB Output is correct
20 Correct 11 ms 23764 KB Output is correct
21 Correct 12 ms 23764 KB Output is correct
22 Correct 11 ms 23764 KB Output is correct
23 Correct 271 ms 63400 KB Output is correct
24 Incorrect 11 ms 23764 KB Solution announced impossible, but it is possible.
25 Halted 0 ms 0 KB -