oj.uz

Submission #813585

# Submission time Handle Problem Language Result Execution time Memory
813585 2023-08-07T22:29:02 Z Username4132 Fountain Parks (IOI21_parks) C++17
5 / 100
 401 ms 145584 KB 
#include "parks.h"
#include <iostream>
#include <vector>
#include<map>
#include<algorithm>
#include<cassert>
using namespace std;
using pii = pair<int, int>;
using ll = long long;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define dforn(i, n) for(int i=n-1; i>=0; --i)
#define dforsn(i, s, n) for(int i=n-1; i>=s; --i)
#define PB push_back
#define F first
#define S second
#define MP make_pair

const int MAXN = 200010;
int n, eind, bi, curi, X[MAXN], Y[MAXN];
bool vis1[MAXN], vis2[MAXN], vis3[MAXN];
pii ptsInd[MAXN];
map<pii, int> mp;
map<pii, int> ben;
vector<pii> g1[MAXN], draw;
vector<int> g2[MAXN];
vector<int> g3[MAXN];
pii nam[MAXN];

int getInd(pii b){
    auto itr = ben.find(b);
    if(itr!=ben.end()) return itr->S;
    else{
        ben[b]=bi;
        ptsInd[bi]=b;
        ++bi;
        return bi-1;
    }
}

void sed(int u, int v){
    int ind = curi++;
    nam[ind] = {u, v};
    int ux = X[u], uy = Y[u];
    int vx = X[v], vy = Y[v];

    if(ux==vx){
        if(uy>vy) swap(uy, vy);
        int i = getInd({ux-1, uy+1});
        int j = getInd({ux+1, uy+1});
        g2[ind].PB(i), g2[ind].PB(j);
        g3[i].PB(ind), g3[j].PB(ind);
    }
    else{
        if(ux>vx) swap(ux, vx);
        int i = getInd({ux+1, uy-1});
        int j = getInd({ux+1, uy+1});
        g2[ind].PB(i), g2[ind].PB(j);
        g3[i].PB(ind), g3[j].PB(ind);
    }

}

void dfs1(int v){
    vis1[v]=true;
    for(pii to:g1[v]) if(!vis1[to.F]){
        sed(v, to.F);
        dfs1(to.F);
    }

}

void dfs2(int v, bool flag){
    if(!flag){
        vis2[v]=true;
        int cn = 0;
        for(int to:g2[v]) if(!vis3[to]){
            if(!cn) draw.PB({v, to});
            dfs2(to, !flag);
            ++cn;
        }
    }
    else{
        vis3[v]=true;
        for(int to:g3[v]) if(!vis2[to]) dfs2(to, !flag);
    }
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    n = (int)x.size();
    forn(i, n){
        mp[MP(x[i], y[i])] = i;
        X[i]=x[i];
        Y[i]=y[i];
    }

    for(auto el:mp){
        auto it = mp.find(MP(el.F.F + 2, el.F.S));
        if(it!=mp.end()){
            g1[el.S].PB(MP(it->S, eind));
            g1[it->S].PB(MP(el.S, eind));
            ++eind;
        }
        it = mp.find({el.F.F, el.F.S + 2});
        if(it!=mp.end()){
            g1[el.S].PB(MP(it->S, eind));
            g1[it->S].PB(MP(el.S, eind));
            ++eind;
        }
    }


    dfs1(0);

    bool possible=true;
    forn(i, n) possible&=vis1[i];
    if(!possible){
        return 0;
    }

    forn(el, curi) if(!vis2[el]) dfs2(el, false);

    vector<int> u, v, a, b;

    for(pii el:draw){
        u.PB(nam[el.F].F);
        v.PB(nam[el.F].S);
        a.PB(ptsInd[el.S].F);
        b.PB(ptsInd[el.S].S);
    }

    build(u, v, a, b);
    return 1;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 9 ms 14340 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 196 ms 62176 KB Output is correct
10 Correct 21 ms 19284 KB Output is correct
11 Correct 99 ms 40216 KB Output is correct
12 Correct 30 ms 21760 KB Output is correct
13 Correct 56 ms 28380 KB Output is correct
14 Correct 8 ms 14636 KB Output is correct
15 Correct 12 ms 14676 KB Output is correct
16 Correct 191 ms 60288 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 9 ms 14340 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 196 ms 62176 KB Output is correct
10 Correct 21 ms 19284 KB Output is correct
11 Correct 99 ms 40216 KB Output is correct
12 Correct 30 ms 21760 KB Output is correct
13 Correct 56 ms 28380 KB Output is correct
14 Correct 8 ms 14636 KB Output is correct
15 Correct 12 ms 14676 KB Output is correct
16 Correct 191 ms 60288 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 7 ms 14420 KB Output is correct
21 Correct 7 ms 14420 KB Output is correct
22 Correct 7 ms 14420 KB Output is correct
23 Runtime error 323 ms 145584 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 9 ms 14340 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 196 ms 62176 KB Output is correct
10 Correct 21 ms 19284 KB Output is correct
11 Correct 99 ms 40216 KB Output is correct
12 Correct 30 ms 21760 KB Output is correct
13 Correct 56 ms 28380 KB Output is correct
14 Correct 8 ms 14636 KB Output is correct
15 Correct 12 ms 14676 KB Output is correct
16 Correct 191 ms 60288 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 7 ms 14420 KB Output is correct
21 Correct 7 ms 14420 KB Output is correct
22 Correct 7 ms 14420 KB Output is correct
23 Runtime error 323 ms 145584 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 9 ms 14340 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 196 ms 62176 KB Output is correct
10 Correct 21 ms 19284 KB Output is correct
11 Correct 99 ms 40216 KB Output is correct
12 Correct 30 ms 21760 KB Output is correct
13 Correct 56 ms 28380 KB Output is correct
14 Correct 8 ms 14636 KB Output is correct
15 Correct 12 ms 14676 KB Output is correct
16 Correct 191 ms 60288 KB Output is correct
17 Correct 7 ms 14412 KB Output is correct
18 Correct 7 ms 14428 KB Output is correct
19 Correct 9 ms 14420 KB Output is correct
20 Correct 401 ms 121232 KB Output is correct
21 Correct 379 ms 102756 KB Output is correct
22 Correct 400 ms 102728 KB Output is correct
23 Runtime error 265 ms 130236 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 9 ms 14340 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 196 ms 62176 KB Output is correct
10 Correct 21 ms 19284 KB Output is correct
11 Correct 99 ms 40216 KB Output is correct
12 Correct 30 ms 21760 KB Output is correct
13 Correct 56 ms 28380 KB Output is correct
14 Correct 8 ms 14636 KB Output is correct
15 Correct 12 ms 14676 KB Output is correct
16 Correct 191 ms 60288 KB Output is correct
17 Runtime error 308 ms 135688 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14432 KB Output is correct
3 Correct 7 ms 14420 KB Output is correct
4 Correct 7 ms 14420 KB Output is correct
5 Correct 9 ms 14420 KB Output is correct
6 Correct 9 ms 14340 KB Output is correct
7 Correct 7 ms 14420 KB Output is correct
8 Correct 7 ms 14420 KB Output is correct
9 Correct 196 ms 62176 KB Output is correct
10 Correct 21 ms 19284 KB Output is correct
11 Correct 99 ms 40216 KB Output is correct
12 Correct 30 ms 21760 KB Output is correct
13 Correct 56 ms 28380 KB Output is correct
14 Correct 8 ms 14636 KB Output is correct
15 Correct 12 ms 14676 KB Output is correct
16 Correct 191 ms 60288 KB Output is correct
17 Correct 8 ms 14420 KB Output is correct
18 Correct 8 ms 14420 KB Output is correct
19 Correct 8 ms 14420 KB Output is correct
20 Correct 7 ms 14420 KB Output is correct
21 Correct 7 ms 14420 KB Output is correct
22 Correct 7 ms 14420 KB Output is correct
23 Runtime error 323 ms 145584 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -