oj.uz

Submission #813133

# Submission time Handle Problem Language Result Execution time Memory
813133 2023-08-07T13:47:05 Z penguinman Fountain Parks (IOI21_parks) C++17
5 / 100
 1856 ms 127032 KB 
#include "parks.h"

#include <bits/stdc++.h>

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = int;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
using std::endl;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define all(a) a.begin(),a.end()

int construct_roads(std::vector<int> x, std::vector<int> y) {
    {
        vi u,v,a,b;
        vi par(x.size());
        rep(i,0,x.size()) par[i] = i;
        std::function<ll(ll)> root = [&](ll now){
            if(par[now] == now) return now;
            return par[now] = root(par[now]);
        };
        std::map<ll,std::map<ll,ll>> X, Y;
        rep(i,0,x.size()) X[x[i]][y[i]] = Y[y[i]][x[i]] = i;
        std::set<pii> used;
        for(auto V: X){
            for(auto el: V.second){
                if(V.second.count(el.first+2)){
                    ll now = el.second;
                    ll next = V.second[el.first+2];
                    if(root(now) == root(next)) continue;
                    par[root(now)] = root(next);
                    vi P = {1,-1};
                    rep(i,0,2){
                        ll ry = el.first+1;
                        ll rx = V.first+P[i];
                        if((rx+ry)%4 == 0){
                            used.insert(mp(rx, ry));
                            u.pb(now);
                            v.pb(next);
                            a.pb(rx);
                            b.pb(ry);
                        }
                    }
                }
            }
        }
        for(auto V: Y){
            for(auto el: V.second){
                if(V.second.count(el.first+2)){
                    ll now = el.second;
                    ll next = V.second[el.first+2];
                    if(root(now) == root(next)) continue;
                    par[root(now)] = root(next);
                    vi P = {1,-1};
                    rep(i,0,2){
                        ll rx = el.first+1;
                        ll ry = V.first+P[i];
                        if(!used.count(mp(rx,ry))){
                            used.insert(mp(rx, ry));
                            u.pb(now);
                            v.pb(next);
                            a.pb(rx);
                            b.pb(ry);
                        }
                    }
                }
            }
        }
        if(u.size()+1 == x.size()){
            build(u,v,a,b);
            return 1;
        }
    }
    if(*max_element(all(x)) <= 6){
        vector<std::map<ll,ll>> X(7);
        rep(i,0,x.size()){
            X[x[i]][y[i]] = i;
        }
        vi u,v,a,b;
        vi par(x.size());
        rep(i,0,x.size()) par[i] = i;
        std::function<ll(ll)> root = [&](ll now){
            if(par[now] == now) return now;
            return par[now] = root(par[now]);
        };
        for(auto el: X[2]){
            if(X[2].count(el.first+2)){
                u.pb(el.second);
                ll next = X[2][el.first+2];
                v.pb(next);
                a.pb(1);
                b.pb(el.first+1);
                par[root(el.second)] = root(next);
            }
        }
        for(auto el: X[6]){
            if(X[6].count(el.first+2)){
                u.pb(el.second);
                ll next = X[6][el.first+2];
                v.pb(next);
                a.pb(7);
                b.pb(el.first+1);
                par[root(el.second)] = root(next);
            }
        }
        std::set<pii> used;
        for(auto el: X[4]){
            if(X[4].count(el.first+2)){
                ll next = X[4][el.first+2];
                par[root(next)] = root(el.second);
                ll rx = -1, ry = -1;
                if(el.first%4 == 0) rx = 3, ry = el.first+1;
                if(el.first%4 == 2) rx = 5, ry = el.first+1;
                used.insert(mp(rx, ry));
                u.pb(el.second);
                v.pb(next);
                a.pb(rx);
                b.pb(ry);
            }
        }
        for(auto el: X[4]){
            if(X[2].count(el.first)){
                ll next = X[2][el.first];
                if(root(next) != root(el.second)){
                    par[root(next)] = root(el.second);
                    u.pb(el.second);
                    v.pb(next);
                    ll rx = -1, ry = -1;
                    if(!used.count(mp(3,el.first-1))) rx = 3, ry = el.first-1;
                    if(!used.count(mp(3,el.first+1))) rx = 3, ry = el.first+1;
                    assert(rx != -1);
                    a.pb(rx);
                    b.pb(ry);
                    used.insert(mp(rx, ry));
                }
            }
            if(X[6].count(el.first)){
                ll next = X[6][el.first];
                if(root(next) != root(el.second)){
                    par[root(next)] = root(el.second);
                    u.pb(el.second);
                    v.pb(next);
                    ll rx = -1, ry = -1;
                    if(!used.count(mp(5,el.first-1))) rx = 5, ry = el.first-1;
                    if(!used.count(mp(5,el.first+1))) rx = 5, ry = el.first+1;
                    assert(rx != -1);
                    a.pb(rx);
                    b.pb(ry);
                    used.insert(mp(rx, ry));
                }
            }
        }
        if(u.size()+1 == x.size()){
            build(u,v,a,b);
            return 1;
        }
        else return 0;
    }
    std::map<pii,ll> xy;
    std::map<pii,ll> rev;
    rep(i,0,x.size()) xy[mp(x[i],y[i])] = i;
    ll cnt__ = 0;
    rep(i,0,x.size()){
        vi P = {2,0}, Q = {0,2};
        vi R = {0,1}, S = {1,0};
        rep(j,0,2){
            if(xy.count(mp(x[i]+P[j], y[i]+Q[j]))){
                ll mx = x[i]+P[j]/2;
                ll my = y[i]+Q[j]/2;
                rev[mp(mx+R[j], my+S[j])] = rev[mp(mx-R[j],my-S[j])] = 0;
                cnt__++;
            }
        }
    }
    ll N = 0;
    vi rx, ry;
    for(auto &el: rev){
        el.second = N++;
        rx.pb(el.first.first);
        ry.pb(el.first.second);
    }
    vii edge(N);
    vii eu(N), ev(N);
    rep(i,0,x.size()){
        vi P = {2,0}, Q = {0,2};
        vi R = {0,1}, S = {1,0};
        rep(j,0,2){
            if(xy.count(mp(x[i]+P[j], y[i]+Q[j]))){
                ll mx = x[i]+P[j]/2;
                ll my = y[i]+Q[j]/2;
                ll nu = rev[mp(mx+R[j], my+S[j])];
                ll nv = rev[mp(mx-R[j],my-S[j])];
                ll nxy = xy[mp(x[i]+P[j], y[i]+Q[j])];
                edge[nu].pb(nv);
                eu[nu].pb(i);
                ev[nu].pb(nxy);
                edge[nv].pb(nu);
                eu[nv].pb(i);
                ev[nv].pb(nxy);
            }
        }
    }
    vi cnt(N);
    rep(i,0,N) cnt[i] = edge[i].size();
    vi u,v,a,b;
    rep(k,0,N){
        if(cnt[k] != 1) continue;
        cnt[k]--;
        ll now = k;
        while(true){
            ll nex = -1;
            rep(i,0,edge[now].size()){
                ll next = edge[now][i];
                if(cnt[next] == 0) continue;
                u.pb(eu[now][i]);
                v.pb(ev[now][i]);
                a.pb(rx[now]);
                b.pb(ry[now]);
                cnt[next]--;
                if(cnt[next] == 1){
                    cnt[next]--;
                    nex = next;
                }
            }
            if(nex == -1) break;
            now = nex;
        }
    }
    rep(i,0,N){
        if(cnt[i] > 2) return 0;
    }
    rep(i,0,N){
        assert(cnt[i] == 0 || cnt[i] == 2);
        if(cnt[i] == 0) continue;
        cnt[i] = 0;
        ll now = i;
        while(true){
            ll val = -1;
            rep(j,0,edge[now].size()){
                ll next = edge[now][j];
                if(cnt[next] == 0) continue;
                u.pb(eu[now][j]);
                v.pb(ev[now][j]);
                a.pb(rx[now]);
                b.pb(ry[now]);
                val = cnt[next];
                cnt[next] = 0;
                now = next;
                break;
            }
            if(val == -1) break;
        }
        rep(j,0,edge[now].size()){
            ll next = edge[now][j];
            if(next != i) continue;
            u.pb(eu[now][j]);
            v.pb(ev[now][j]);
            a.pb(rx[now]);
            b.pb(ry[now]);
        }
    }
    build(u,v,a,b);
    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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 249 ms 32836 KB Output is correct
10 Correct 11 ms 3540 KB Output is correct
11 Correct 65 ms 17812 KB Output is correct
12 Correct 16 ms 5076 KB Output is correct
13 Correct 57 ms 14656 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 222 ms 32804 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 249 ms 32836 KB Output is correct
10 Correct 11 ms 3540 KB Output is correct
11 Correct 65 ms 17812 KB Output is correct
12 Correct 16 ms 5076 KB Output is correct
13 Correct 57 ms 14656 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 222 ms 32804 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 1 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 249 ms 32836 KB Output is correct
10 Correct 11 ms 3540 KB Output is correct
11 Correct 65 ms 17812 KB Output is correct
12 Correct 16 ms 5076 KB Output is correct
13 Correct 57 ms 14656 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 222 ms 32804 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 1 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 249 ms 32836 KB Output is correct
10 Correct 11 ms 3540 KB Output is correct
11 Correct 65 ms 17812 KB Output is correct
12 Correct 16 ms 5076 KB Output is correct
13 Correct 57 ms 14656 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 222 ms 32804 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 0 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 3
20 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 249 ms 32836 KB Output is correct
10 Correct 11 ms 3540 KB Output is correct
11 Correct 65 ms 17812 KB Output is correct
12 Correct 16 ms 5076 KB Output is correct
13 Correct 57 ms 14656 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 222 ms 32804 KB Output is correct
17 Correct 1819 ms 126132 KB Output is correct
18 Correct 1828 ms 127032 KB Output is correct
19 Correct 471 ms 53408 KB Output is correct
20 Correct 1856 ms 92044 KB Output is correct
21 Correct 1541 ms 100852 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 132 ms 14840 KB Output is correct
24 Incorrect 86 ms 9620 KB Given structure is not connected: There is no path between vertices 0 and 1
25 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 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 0 ms 284 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 249 ms 32836 KB Output is correct
10 Correct 11 ms 3540 KB Output is correct
11 Correct 65 ms 17812 KB Output is correct
12 Correct 16 ms 5076 KB Output is correct
13 Correct 57 ms 14656 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 3 ms 852 KB Output is correct
16 Correct 222 ms 32804 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Incorrect 1 ms 212 KB Tree @(3, 5) appears more than once: for edges on positions 0 and 1
19 Halted 0 ms 0 KB -