oj.uz

Submission #813565

# Submission time Handle Problem Language Result Execution time Memory
813565 2023-08-07T20:22:54 Z Ozy Fountain Parks (IOI21_parks) C++17
5 / 100
 816 ms 73056 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for(int i = (a); i <= (b); i++) 
#define repa(i,a,b) for(int i = (a); i >= (b); i--)
#define pll pair<lli,lli>

#define MAX 200000
//para los pares en general
#define xx first
#define yy second

lli n,a,b,uf[MAX+2],uniones;
lli s[2] = {-1,1};
map<pll,lli> mapa,a_vis,b_vis;
lli dir[8] = {0,-2,0,2,2,0,-2,0};
vector<pll> aristas;
vector<int> u,v,b_x,b_y;

lli sube(lli pos) {
    if (uf[pos] == pos) return pos;
    uf[pos] = sube(uf[pos]);
    return uf[pos];
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    
    n = x.size();
    rep(i,0,n-1) {
        uf[i] = i;
        
        mapa[{x[i],y[i]}] = i;
        rep(j,0,3) {
            a = x[i] + dir[j];
            b = y[i] + dir[j+4];
            if(mapa.find({a,b}) != mapa.end()) {
                aristas.push_back({i,mapa[{a,b}]});
                a = sube(mapa[{a,b}]);
                b = sube(i);

                if (a != b) {
                    uniones++;
                    uf[a] = b;
                }
            }
        }

    }

    if(uniones != n-1) return 0;

    for (auto act : aristas) {
        //debugsl(act.first);
        //debug(act.second);

        while (a_vis.find(act) == a_vis.end()) {
            a_vis[act] = 1;
            swap(act.first,act.second);
            a_vis[act] = 1;

            //opciones para colocar la banca
            pll w = {(x[act.first] + x[act.second])/2, (y[act.first] + y[act.second])/2};
            pll z = {(x[act.first] + x[act.second])/2, (y[act.first] + y[act.second])/2};
            if (x[act.first] == x[act.second]) {
                w.xx++;
                z.xx--;
            }
            else {
                w.yy++;
                z.yy--;
            }

            if (b_vis.find(w) == mapa.end()) { //pongo mi banca en w
                b_vis[w] = 1;

                b_x.push_back(w.xx);
                b_y.push_back(w.yy);
                u.push_back(act.first);
                v.push_back(act.second);
            }
            else {
                b_vis[z] = 1;

                b_x.push_back(z.xx);
                b_y.push_back(z.yy);
                u.push_back(act.first);
                v.push_back(act.second);

                w = z;   
            }

            //busco si es que el esta en una tripleta y continuo la busqueda
            rep(i,0,1) {
                rep(j,0,1) {
                    z.xx = w.xx + s[i];
                    z.yy = w.yy + s[j];

                    if (z.xx == x[act.first] && z.yy == y[act.first]) continue;
                    if (z.xx == x[act.second] && z.yy == y[act.second]) continue;
                    if (mapa.find(z) == mapa.end()) continue;

                    if (z.xx == x[act.first] || z.yy == y[act.first]) act.second = mapa[z];
                    else act.first = mapa[z];
                }
            }

        }
        
    }

    build(u,v,b_x,b_y);
    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 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 216 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 254 ms 36120 KB Output is correct
10 Correct 13 ms 3920 KB Output is correct
11 Correct 91 ms 19548 KB Output is correct
12 Correct 21 ms 5704 KB Output is correct
13 Correct 31 ms 5136 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 448 KB Output is correct
16 Correct 264 ms 36220 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 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 216 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 254 ms 36120 KB Output is correct
10 Correct 13 ms 3920 KB Output is correct
11 Correct 91 ms 19548 KB Output is correct
12 Correct 21 ms 5704 KB Output is correct
13 Correct 31 ms 5136 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 448 KB Output is correct
16 Correct 264 ms 36220 KB Output is correct
17 Incorrect 1 ms 212 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 216 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 254 ms 36120 KB Output is correct
10 Correct 13 ms 3920 KB Output is correct
11 Correct 91 ms 19548 KB Output is correct
12 Correct 21 ms 5704 KB Output is correct
13 Correct 31 ms 5136 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 448 KB Output is correct
16 Correct 264 ms 36220 KB Output is correct
17 Incorrect 1 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 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 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 216 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 254 ms 36120 KB Output is correct
10 Correct 13 ms 3920 KB Output is correct
11 Correct 91 ms 19548 KB Output is correct
12 Correct 21 ms 5704 KB Output is correct
13 Correct 31 ms 5136 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 448 KB Output is correct
16 Correct 264 ms 36220 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 0 ms 212 KB Tree @(199999, 199999) appears more than once: for edges on positions 0 and 1
19 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 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 216 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 254 ms 36120 KB Output is correct
10 Correct 13 ms 3920 KB Output is correct
11 Correct 91 ms 19548 KB Output is correct
12 Correct 21 ms 5704 KB Output is correct
13 Correct 31 ms 5136 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 448 KB Output is correct
16 Correct 264 ms 36220 KB Output is correct
17 Incorrect 816 ms 73056 KB Tree @(100001, 100001) appears more than once: for edges on positions 163158 and 187518
18 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 0 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 312 KB Output is correct
5 Correct 1 ms 312 KB Output is correct
6 Correct 0 ms 308 KB Output is correct
7 Correct 0 ms 216 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 254 ms 36120 KB Output is correct
10 Correct 13 ms 3920 KB Output is correct
11 Correct 91 ms 19548 KB Output is correct
12 Correct 21 ms 5704 KB Output is correct
13 Correct 31 ms 5136 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 448 KB Output is correct
16 Correct 264 ms 36220 KB Output is correct
17 Incorrect 1 ms 212 KB Tree @(3, 3) appears more than once: for edges on positions 0 and 1
18 Halted 0 ms 0 KB -