oj.uz

Submission #811106

# Submission time Handle Problem Language Result Execution time Memory
811106 2023-08-06T23:55:30 Z penguinman Fountain Parks (IOI21_parks) C++17
5 / 100
 3500 ms 123008 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;
                edge[rev[mp(mx+R[j], my+S[j])]].pb(rev[mp(mx-R[j],my-S[j])]);
                eu[rev[mp(mx+R[j], my+S[j])]].pb(i);
                ev[rev[mp(mx+R[j], my+S[j])]].pb(xy[mp(x[i]+P[j], y[i]+Q[j])]);
                edge[rev[mp(mx-R[j],my-S[j])]].pb(rev[mp(mx+R[j], my+S[j])]);
                eu[rev[mp(mx-R[j], my-S[j])]].pb(i);
                ev[rev[mp(mx-R[j], my-S[j])]].pb(xy[mp(x[i]+P[j], y[i]+Q[j])]);
            }
        }
    }
    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 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 296 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 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 594 ms 61720 KB Output is correct
10 Correct 23 ms 6488 KB Output is correct
11 Correct 148 ms 33280 KB Output is correct
12 Correct 36 ms 9404 KB Output is correct
13 Correct 40 ms 9548 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 556 ms 61764 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 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 296 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 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 594 ms 61720 KB Output is correct
10 Correct 23 ms 6488 KB Output is correct
11 Correct 148 ms 33280 KB Output is correct
12 Correct 36 ms 9404 KB Output is correct
13 Correct 40 ms 9548 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 556 ms 61764 KB Output is correct
17 Incorrect 1 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 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 296 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 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 594 ms 61720 KB Output is correct
10 Correct 23 ms 6488 KB Output is correct
11 Correct 148 ms 33280 KB Output is correct
12 Correct 36 ms 9404 KB Output is correct
13 Correct 40 ms 9548 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 556 ms 61764 KB Output is correct
17 Incorrect 1 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 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 296 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 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 594 ms 61720 KB Output is correct
10 Correct 23 ms 6488 KB Output is correct
11 Correct 148 ms 33280 KB Output is correct
12 Correct 36 ms 9404 KB Output is correct
13 Correct 40 ms 9548 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 556 ms 61764 KB Output is correct
17 Correct 1 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 988 ms 76348 KB Output is correct
21 Correct 1194 ms 76008 KB Output is correct
22 Correct 1029 ms 76204 KB Output is correct
23 Correct 1167 ms 105536 KB Output is correct
24 Correct 193 ms 17656 KB Output is correct
25 Correct 486 ms 42556 KB Output is correct
26 Correct 462 ms 42552 KB Output is correct
27 Correct 1529 ms 122908 KB Output is correct
28 Correct 1520 ms 122912 KB Output is correct
29 Correct 1461 ms 122940 KB Output is correct
30 Correct 1473 ms 123008 KB Output is correct
31 Correct 0 ms 212 KB Output is correct
32 Execution timed out 3570 ms 6272 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 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 296 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 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 594 ms 61720 KB Output is correct
10 Correct 23 ms 6488 KB Output is correct
11 Correct 148 ms 33280 KB Output is correct
12 Correct 36 ms 9404 KB Output is correct
13 Correct 40 ms 9548 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 556 ms 61764 KB Output is correct
17 Incorrect 439 ms 42996 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 1 ms 212 KB Output is correct
3 Correct 0 ms 296 KB Output is correct
4 Correct 1 ms 296 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 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 594 ms 61720 KB Output is correct
10 Correct 23 ms 6488 KB Output is correct
11 Correct 148 ms 33280 KB Output is correct
12 Correct 36 ms 9404 KB Output is correct
13 Correct 40 ms 9548 KB Output is correct
14 Correct 1 ms 468 KB Output is correct
15 Correct 2 ms 596 KB Output is correct
16 Correct 556 ms 61764 KB Output is correct
17 Incorrect 1 ms 212 KB Solution announced impossible, but it is possible.
18 Halted 0 ms 0 KB -