oj.uz

Submission #815229

# Submission time Handle Problem Language Result Execution time Memory
815229 2023-08-08T13:21:05 Z blackyuki Fountain Parks (IOI21_parks) C++17
55 / 100
 417 ms 41240 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<bool> vb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define pb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
const ll inf=1001001001001001001;
struct UF{
	ll n;
	vi par,sz;
	UF(ll n_):n(n_),par(n,-1),sz(n,1){}
	void merge(ll a,ll b){
		a=root(a);b=root(b);
		if(a==b)return;
		if(sz[a]>sz[b])swap(a,b);
		par[a]=b;
		sz[b]+=sz[a];
	}
	ll root(ll i){
		if(par[i]==-1)return i;
		par[i]=root(par[i]);
		return par[i];
	}
	bool same(ll a,ll b){
		return root(a)==root(b);
	}
    ll getsz(ll i){
        return sz[root(i)];
    }
};
int construct_roads(std::vector<int> x, std::vector<int> y) {
    ll n=x.size();
    UF uf(n);
    vector<PP> v(n);
    rep(i,n)v[i]=PP(x[i],y[i],i);
    sort(all(v));
    vi dx={2,0},dy={0,2};
    set<P> S;
    vector<int> U, V, A, B;
    rep(i,n)rep(j,2){
        P a(x[i],y[i]),b(x[i]+dx[j],y[i]+dy[j]);
        ll l=lb(v,PP(b.fi,b.se,-1));
        if(l==n)continue;
        l=get<2>(v[l]);
        if(P(x[l],y[l])!=b)continue;
        P c((a.fi+b.fi)/2,(a.se+b.se)/2);
        if(a.fi==b.fi){
            if((a.fi+a.se)%4==0)c.fi--;
            else c.fi++;
        }
        else{
            if((a.fi+a.se)%4==0)c.se++;
            else c.se--;
        }
            uf.merge(i,l);
        if(S.insert(c).se){
            U.pb(i);
            V.pb(l);
            A.pb(c.fi);
            B.pb(c.se);
        }
    }
    if(uf.getsz(0)<n)return 0;
    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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 108 ms 17580 KB Output is correct
10 Correct 7 ms 2004 KB Output is correct
11 Correct 37 ms 9516 KB Output is correct
12 Correct 10 ms 2912 KB Output is correct
13 Correct 19 ms 6536 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 109 ms 17548 KB Output is correct

Subtask #2
10.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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 108 ms 17580 KB Output is correct
10 Correct 7 ms 2004 KB Output is correct
11 Correct 37 ms 9516 KB Output is correct
12 Correct 10 ms 2912 KB Output is correct
13 Correct 19 ms 6536 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 109 ms 17548 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 331 ms 34756 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 97 ms 14112 KB Output is correct
29 Correct 159 ms 21040 KB Output is correct
30 Correct 260 ms 28000 KB Output is correct
31 Correct 344 ms 34800 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 300 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 292 KB Output is correct
43 Correct 2 ms 596 KB Output is correct
44 Correct 2 ms 724 KB Output is correct
45 Correct 115 ms 17584 KB Output is correct
46 Correct 185 ms 25372 KB Output is correct
47 Correct 194 ms 25296 KB Output is correct

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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 108 ms 17580 KB Output is correct
10 Correct 7 ms 2004 KB Output is correct
11 Correct 37 ms 9516 KB Output is correct
12 Correct 10 ms 2912 KB Output is correct
13 Correct 19 ms 6536 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 109 ms 17548 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 331 ms 34756 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 97 ms 14112 KB Output is correct
29 Correct 159 ms 21040 KB Output is correct
30 Correct 260 ms 28000 KB Output is correct
31 Correct 344 ms 34800 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 300 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 292 KB Output is correct
43 Correct 2 ms 596 KB Output is correct
44 Correct 2 ms 724 KB Output is correct
45 Correct 115 ms 17584 KB Output is correct
46 Correct 185 ms 25372 KB Output is correct
47 Correct 194 ms 25296 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 0 ms 212 KB Output is correct
55 Incorrect 373 ms 34760 KB Given structure is not connected: There is no path between vertices 0 and 10587
56 Halted 0 ms 0 KB -

Subtask #4
20.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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 108 ms 17580 KB Output is correct
10 Correct 7 ms 2004 KB Output is correct
11 Correct 37 ms 9516 KB Output is correct
12 Correct 10 ms 2912 KB Output is correct
13 Correct 19 ms 6536 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 109 ms 17548 KB Output is correct
17 Correct 0 ms 304 KB Output is correct
18 Correct 1 ms 304 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 267 ms 35628 KB Output is correct
21 Correct 304 ms 35476 KB Output is correct
22 Correct 278 ms 35416 KB Output is correct
23 Correct 237 ms 29980 KB Output is correct
24 Correct 99 ms 12968 KB Output is correct
25 Correct 256 ms 28464 KB Output is correct
26 Correct 253 ms 28576 KB Output is correct
27 Correct 289 ms 34712 KB Output is correct
28 Correct 302 ms 34952 KB Output is correct
29 Correct 312 ms 34800 KB Output is correct
30 Correct 315 ms 34804 KB Output is correct
31 Correct 0 ms 296 KB Output is correct
32 Correct 15 ms 2824 KB Output is correct
33 Correct 47 ms 6968 KB Output is correct
34 Correct 304 ms 35728 KB Output is correct
35 Correct 8 ms 1720 KB Output is correct
36 Correct 44 ms 7556 KB Output is correct
37 Correct 99 ms 14864 KB Output is correct
38 Correct 95 ms 14588 KB Output is correct
39 Correct 141 ms 19708 KB Output is correct
40 Correct 193 ms 25096 KB Output is correct
41 Correct 245 ms 30452 KB Output is correct
42 Correct 307 ms 35728 KB Output is correct
43 Correct 1 ms 212 KB Output is correct
44 Correct 0 ms 212 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 0 ms 212 KB Output is correct
47 Correct 0 ms 212 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 1 ms 304 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 1 ms 300 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 0 ms 304 KB Output is correct
54 Correct 2 ms 468 KB Output is correct
55 Correct 2 ms 724 KB Output is correct
56 Correct 136 ms 17536 KB Output is correct
57 Correct 199 ms 25316 KB Output is correct
58 Correct 206 ms 25284 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 0 ms 296 KB Output is correct
62 Correct 319 ms 34752 KB Output is correct
63 Correct 311 ms 34832 KB Output is correct
64 Correct 391 ms 34592 KB Output is correct
65 Correct 4 ms 852 KB Output is correct
66 Correct 6 ms 1340 KB Output is correct
67 Correct 147 ms 17508 KB Output is correct
68 Correct 261 ms 26172 KB Output is correct
69 Correct 389 ms 34808 KB Output is correct

Subtask #5
20.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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 108 ms 17580 KB Output is correct
10 Correct 7 ms 2004 KB Output is correct
11 Correct 37 ms 9516 KB Output is correct
12 Correct 10 ms 2912 KB Output is correct
13 Correct 19 ms 6536 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 109 ms 17548 KB Output is correct
17 Correct 350 ms 35160 KB Output is correct
18 Correct 379 ms 35268 KB Output is correct
19 Correct 350 ms 35528 KB Output is correct
20 Correct 417 ms 41240 KB Output is correct
21 Correct 327 ms 32676 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 36 ms 6108 KB Output is correct
24 Correct 20 ms 3516 KB Output is correct
25 Correct 71 ms 11440 KB Output is correct
26 Correct 136 ms 19488 KB Output is correct
27 Correct 142 ms 20112 KB Output is correct
28 Correct 185 ms 25208 KB Output is correct
29 Correct 253 ms 30192 KB Output is correct
30 Correct 297 ms 34976 KB Output is correct
31 Correct 362 ms 39976 KB Output is correct
32 Correct 360 ms 39216 KB Output is correct
33 Correct 296 ms 34848 KB Output is correct
34 Correct 4 ms 976 KB Output is correct
35 Correct 6 ms 1620 KB Output is correct
36 Correct 125 ms 18572 KB Output is correct
37 Correct 230 ms 28016 KB Output is correct
38 Correct 339 ms 37116 KB Output is correct

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 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 300 KB Output is correct
8 Correct 1 ms 296 KB Output is correct
9 Correct 108 ms 17580 KB Output is correct
10 Correct 7 ms 2004 KB Output is correct
11 Correct 37 ms 9516 KB Output is correct
12 Correct 10 ms 2912 KB Output is correct
13 Correct 19 ms 6536 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 109 ms 17548 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 300 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 331 ms 34756 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 3 ms 852 KB Output is correct
27 Correct 3 ms 852 KB Output is correct
28 Correct 97 ms 14112 KB Output is correct
29 Correct 159 ms 21040 KB Output is correct
30 Correct 260 ms 28000 KB Output is correct
31 Correct 344 ms 34800 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 1 ms 212 KB Output is correct
34 Correct 0 ms 212 KB Output is correct
35 Correct 0 ms 300 KB Output is correct
36 Correct 0 ms 212 KB Output is correct
37 Correct 0 ms 212 KB Output is correct
38 Correct 0 ms 212 KB Output is correct
39 Correct 0 ms 212 KB Output is correct
40 Correct 0 ms 212 KB Output is correct
41 Correct 0 ms 212 KB Output is correct
42 Correct 0 ms 292 KB Output is correct
43 Correct 2 ms 596 KB Output is correct
44 Correct 2 ms 724 KB Output is correct
45 Correct 115 ms 17584 KB Output is correct
46 Correct 185 ms 25372 KB Output is correct
47 Correct 194 ms 25296 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 0 ms 212 KB Output is correct
52 Correct 0 ms 212 KB Output is correct
53 Correct 1 ms 212 KB Output is correct
54 Correct 0 ms 212 KB Output is correct
55 Incorrect 373 ms 34760 KB Given structure is not connected: There is no path between vertices 0 and 10587
56 Halted 0 ms 0 KB -