oj.uz

Submission #817206

# Submission time Handle Problem Language Result Execution time Memory
817206 2023-08-09T10:36:06 Z penguinman Fountain Parks (IOI21_parks) C++17
5 / 100
 608 ms 56272 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((rx+ry)%4 == 2){
                            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 232 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 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 1 ms 300 KB Output is correct
9 Correct 258 ms 32760 KB Output is correct
10 Correct 10 ms 3540 KB Output is correct
11 Correct 67 ms 17692 KB Output is correct
12 Correct 17 ms 5176 KB Output is correct
13 Correct 62 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 234 ms 32836 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 232 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 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 1 ms 300 KB Output is correct
9 Correct 258 ms 32760 KB Output is correct
10 Correct 10 ms 3540 KB Output is correct
11 Correct 67 ms 17692 KB Output is correct
12 Correct 17 ms 5176 KB Output is correct
13 Correct 62 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 234 ms 32836 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 232 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 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 1 ms 300 KB Output is correct
9 Correct 258 ms 32760 KB Output is correct
10 Correct 10 ms 3540 KB Output is correct
11 Correct 67 ms 17692 KB Output is correct
12 Correct 17 ms 5176 KB Output is correct
13 Correct 62 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 234 ms 32836 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 232 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 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 1 ms 300 KB Output is correct
9 Correct 258 ms 32760 KB Output is correct
10 Correct 10 ms 3540 KB Output is correct
11 Correct 67 ms 17692 KB Output is correct
12 Correct 17 ms 5176 KB Output is correct
13 Correct 62 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 234 ms 32836 KB Output is correct
17 Correct 1 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 232 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 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 1 ms 300 KB Output is correct
9 Correct 258 ms 32760 KB Output is correct
10 Correct 10 ms 3540 KB Output is correct
11 Correct 67 ms 17692 KB Output is correct
12 Correct 17 ms 5176 KB Output is correct
13 Correct 62 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 234 ms 32836 KB Output is correct
17 Correct 608 ms 56272 KB Output is correct
18 Correct 524 ms 56108 KB Output is correct
19 Correct 461 ms 53528 KB Output is correct
20 Correct 404 ms 42572 KB Output is correct
21 Correct 431 ms 38332 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 42 ms 7600 KB Output is correct
24 Incorrect 79 ms 9572 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 232 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 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 1 ms 300 KB Output is correct
9 Correct 258 ms 32760 KB Output is correct
10 Correct 10 ms 3540 KB Output is correct
11 Correct 67 ms 17692 KB Output is correct
12 Correct 17 ms 5176 KB Output is correct
13 Correct 62 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 234 ms 32836 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 -