oj.uz

Submission #811107

# Submission time Handle Problem Language Result Execution time Memory
811107 2023-08-06T23:58:41 Z penguinman Fountain Parks (IOI21_parks) C++17
5 / 100
 3500 ms 121400 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) {
    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__++;
            }
        }
    }
    if(cnt__ != ll(x.size()-1)) return 0;
    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] = 1;
        ll now = i;
        while(true){
            ll val = -1;
            rep(j,0,edge[now].size()){
                ll next = edge[now][i];
                if(cnt[next] == 0) continue;
                u.pb(eu[now][j]);
                v.pb(ev[now][j]);
                a.pb(rx[now]);
                b.pb(ry[now]);
                val = next;
                cnt[next] = 0;
                break;
            }
            if(val == 1) break;
        }
    }
    build(u,v,a,b);
    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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 535 ms 60900 KB Output is correct
10 Correct 18 ms 6484 KB Output is correct
11 Correct 114 ms 32828 KB Output is correct
12 Correct 31 ms 9308 KB Output is correct
13 Correct 39 ms 9164 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 512 ms 60924 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 535 ms 60900 KB Output is correct
10 Correct 18 ms 6484 KB Output is correct
11 Correct 114 ms 32828 KB Output is correct
12 Correct 31 ms 9308 KB Output is correct
13 Correct 39 ms 9164 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 512 ms 60924 KB Output is correct
17 Incorrect 0 ms 212 KB Solution announced impossible, but it is possible.
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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 535 ms 60900 KB Output is correct
10 Correct 18 ms 6484 KB Output is correct
11 Correct 114 ms 32828 KB Output is correct
12 Correct 31 ms 9308 KB Output is correct
13 Correct 39 ms 9164 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 512 ms 60924 KB Output is correct
17 Incorrect 0 ms 212 KB Solution announced impossible, but it is possible.
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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 535 ms 60900 KB Output is correct
10 Correct 18 ms 6484 KB Output is correct
11 Correct 114 ms 32828 KB Output is correct
12 Correct 31 ms 9308 KB Output is correct
13 Correct 39 ms 9164 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 512 ms 60924 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 895 ms 73676 KB Output is correct
21 Correct 996 ms 73664 KB Output is correct
22 Correct 847 ms 73672 KB Output is correct
23 Correct 983 ms 103828 KB Output is correct
24 Correct 193 ms 15904 KB Output is correct
25 Correct 505 ms 41004 KB Output is correct
26 Correct 457 ms 40828 KB Output is correct
27 Correct 1446 ms 121304 KB Output is correct
28 Correct 1384 ms 121352 KB Output is correct
29 Correct 1292 ms 121300 KB Output is correct
30 Correct 1422 ms 121400 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Execution timed out 3554 ms 6084 KB Time limit exceeded
33 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 535 ms 60900 KB Output is correct
10 Correct 18 ms 6484 KB Output is correct
11 Correct 114 ms 32828 KB Output is correct
12 Correct 31 ms 9308 KB Output is correct
13 Correct 39 ms 9164 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 512 ms 60924 KB Output is correct
17 Incorrect 463 ms 40904 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 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 0 ms 212 KB Output is correct
9 Correct 535 ms 60900 KB Output is correct
10 Correct 18 ms 6484 KB Output is correct
11 Correct 114 ms 32828 KB Output is correct
12 Correct 31 ms 9308 KB Output is correct
13 Correct 39 ms 9164 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 512 ms 60924 KB Output is correct
17 Incorrect 0 ms 212 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -