oj.uz

Submission #1058814

# Submission time Handle Problem Language Result Execution time Memory
1058814 2024-08-14T14:04:59 Z LittleOrange Fountain Parks (IOI21_parks) C++17
55 / 100
 2989 ms 114388 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
struct dsu{
    ll n;
    vector<ll> p;
    dsu(ll N):n(N),p(N,-1){}
    ll g(ll i){
        return p[i]<0?i:p[i]=g(p[i]);
    }
    bool m(ll a, ll b){
        a = g(a);
        b = g(b);
        if(a==b) return false;
        if(p[a]>p[b]) swap(a,b);
        p[a]+=p[b];
        p[b]=a;
        return true;
    }
};
struct obj{
    ll x,y,i;
    bool operator<(const obj &o) const{
        return x!=o.x?x<o.x:y<o.y;
    }
    obj operator+(const obj &o) const{
        return {x+o.x,y+o.y,i};
    }
    obj operator-(const obj &o) const{
        return {x-o.x,y-o.y,i};
    }
    bool operator==(const obj &o) const{
        return x==o.x&&y==o.y;
    }
    bool operator!=(const obj &o) const{
        return x!=o.x||y!=o.y;
    }
    obj turn() const{
        return {y,-x,i};
    }
};
using pos = obj;
struct pr{
    ll i,c;
    bool operator<(const pr &o) const{
        return c>o.c;
    }
};
struct ppr{
    pos a,b;
    ll w;
    bool operator<(const ppr &o) const{
        return w>o.w;
    }
};
ostream& operator<<(ostream& o, const pos &p){
    return o << "(" << p.x << "," << p.y << ";" << p.i << ")";
}
pos mid(const pos &a, const pos &b){
    return {(a.x+b.x)/2,(a.y+b.y)/2,0};
}
array<pos,2> mids(const pos &a, const pos &b){
    pos m = mid(a,b);
    array<pos,2> r = {m+(a-m).turn(),m+(b-m).turn()};
    ////cerr << "mids of " << a << " " << b << " -> " << r[0] << " " << r[1] << "\n";
    return r;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
    mt19937_64 mt(random_device{}());
    ll n = x.size();
    vector<obj> fs = {{0,2,0},{0,-2,0},{2,0,0},{-2,0,0}};
    if (x.size() == 1) {
	    build({}, {}, {}, {});
        return 1;
    }
    ll t0 = time(0);
    while(time(0)<t0+3){
        vector<ll> ans_u,ans_v,ans_a,ans_b;
        vector<obj> a(n);
        for(ll i = 0;i<n;i++){
            a[i] = {x[i],y[i],i};
        }
        //shuffle(ord.begin(),ord.end(),mt);
        sort(a.begin(),a.end());
        dsu d(n);
        vector<pair<pos,pos>> cons;
        vector<pair<pos,pos>> ord;
        for(pos u : a){
            for(pos f : fs){
                pos v = u+f;
                auto it = lower_bound(a.begin(),a.end(),v);
                if (it==a.end()||*it!=v) continue;
                v = *it;
                ord.push_back({u,v});
            }
        }
        shuffle(ord.begin(),ord.end(),mt);
        vector<ll> h(n,0);
        {
            priority_queue<ppr> q;
            for(auto [u,v] : ord) q.push({u,v,0});
            while(!q.empty()){
                auto [u,v,c] = q.top();q.pop();
                if (max(h[u.i],h[v.i])>c) continue;
                if(d.m(u.i,v.i)){
                    h[u.i]++;
                    h[v.i]++;
                    //cerr << "con " << u << " " << v << "\n";
                    cons.push_back({u,v});
                    {
                        ll hh = h[u.i];
                        pos p1 = u;
                        for(pos f : fs){
                            pos p2 = p1+f;
                            auto it = lower_bound(a.begin(),a.end(),p2);
                            if (it==a.end()||*it!=p2) continue;
                            p2 = *it;
                            q.push({p1,p2,hh});
                        }
                    }
                    {
                        ll hh = h[v.i];
                        pos p1 = v;
                        for(pos f : fs){
                            pos p2 = p1+f;
                            auto it = lower_bound(a.begin(),a.end(),p2);
                            if (it==a.end()||*it!=p2) continue;
                            p2 = *it;
                            q.push({p1,p2,hh});
                        }
                    }
                }
            }
        }
        if(cons.size()<n-1) return 0;
        vector<pos> v;
        for(auto [p0,p1] : cons){
            for(pos p : mids(p0,p1)) v.push_back(p);
        }
        sort(v.begin(),v.end());
        v.erase(unique(v.begin(),v.end()),v.end());
        ll m = v.size();
        vector<pair<pos,pos>> ops;
        vector<vector<ll>> con(m);
        vector<ll> u(n-1,0);
        for(auto [p0,p1] : cons){
            auto o = mids(p0,p1);
            ll i = lower_bound(v.begin(),v.end(),o[0])-v.begin();
            ll j = lower_bound(v.begin(),v.end(),o[1])-v.begin();
            pair<pos,pos> op = {min(o[0],o[1]),max(o[0],o[1])};
            //cerr << "ops " << op.first << " " << op.second << "\n";
            ops.push_back(op);
            con[i].push_back(j);
            con[j].push_back(i);
        }
        sort(ops.begin(),ops.end());
        vector<ll> um(m,0);
        //shuffle(idl.begin(),idl.end(),mt);
        priority_queue<pr> q;
        for(ll i = 0;i<m;i++) q.push({i,con[i].size()});
        while(!q.empty()){
            auto [i,_] = q.top();q.pop();
            if (um[i]) continue;
            shuffle(con[i].begin(),con[i].end(),mt);
            for(ll j : con[i]){
                pair<pos,pos> op = {min(v[i],v[j]),max(v[i],v[j])};
                //cerr << "test " << op.first << " " << op.second << "\n";
                auto it = lower_bound(ops.begin(),ops.end(),op);
                if (it==ops.end()) {
                    //cerr << "error 1\n";
                    continue;
                }
                //cerr << "got " << (*it).first << " " << (*it).second << "\n";
                if ((*it)!=op) {
                    //cerr << "error 2\n";
                    continue;
                }
                ll idx = it-ops.begin();
                //cerr << "idx= " << idx << "\n";
                if(u[idx]) {
                    //cerr << "error 3\n";
                    continue;
                }
                u[idx] = 1;
                um[i] = 1;
                for(ll z = 0;z<con[j].size();z++) if(con[j][z]==i){
                    con[j].erase(con[j].begin()+z);
                    break;
                }
                q.push({j,con[j].size()});
                pos p = v[i];
                ans_a.push_back(p.x);
                ans_b.push_back(p.y);
                auto os = mids(v[i],v[j]);
                //cerr << "use " << p << " from " << os[0] << " " << os[1] << "\n";
                ll idx1 = (*lower_bound(a.begin(),a.end(),os[0])).i;
                ll idx2 = (*lower_bound(a.begin(),a.end(),os[1])).i;
                ans_u.push_back(idx1);
                ans_v.push_back(idx2);
                break;
            }
        }
        if(ans_u.size()<n-1) continue;
        build(ans_u,ans_v,ans_a,ans_b);
        return 1;
    }
    return 0;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:136:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<obj, obj> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  136 |         if(cons.size()<n-1) return 0;
      |            ~~~~~~~~~~~^~~~
parks.cpp:161:52: warning: narrowing conversion of '(& con.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)i)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} [-Wnarrowing]
  161 |         for(ll i = 0;i<m;i++) q.push({i,con[i].size()});
      |                                         ~~~~~~~~~~~^~
parks.cpp:187:31: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  187 |                 for(ll z = 0;z<con[j].size();z++) if(con[j][z]==i){
      |                              ~^~~~~~~~~~~~~~
parks.cpp:191:38: warning: narrowing conversion of '(& con.std::vector<std::vector<int> >::operator[](((std::vector<std::vector<int> >::size_type)j)))->std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'll' {aka 'int'} [-Wnarrowing]
  191 |                 q.push({j,con[j].size()});
      |                           ~~~~~~~~~~~^~
parks.cpp:204:24: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
  204 |         if(ans_u.size()<n-1) continue;
      |            ~~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 242 ms 36804 KB Output is correct
10 Correct 23 ms 3884 KB Output is correct
11 Correct 119 ms 19296 KB Output is correct
12 Correct 31 ms 5432 KB Output is correct
13 Correct 49 ms 10692 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 255 ms 37272 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 242 ms 36804 KB Output is correct
10 Correct 23 ms 3884 KB Output is correct
11 Correct 119 ms 19296 KB Output is correct
12 Correct 31 ms 5432 KB Output is correct
13 Correct 49 ms 10692 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 255 ms 37272 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 656 ms 68624 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 3 ms 956 KB Output is correct
26 Correct 4 ms 1368 KB Output is correct
27 Correct 6 ms 1908 KB Output is correct
28 Correct 238 ms 29880 KB Output is correct
29 Correct 333 ms 39972 KB Output is correct
30 Correct 518 ms 56768 KB Output is correct
31 Correct 633 ms 69228 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 436 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 860 KB Output is correct
44 Correct 4 ms 1052 KB Output is correct
45 Correct 271 ms 32736 KB Output is correct
46 Correct 392 ms 50984 KB Output is correct
47 Correct 383 ms 50956 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 242 ms 36804 KB Output is correct
10 Correct 23 ms 3884 KB Output is correct
11 Correct 119 ms 19296 KB Output is correct
12 Correct 31 ms 5432 KB Output is correct
13 Correct 49 ms 10692 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 255 ms 37272 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 656 ms 68624 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 3 ms 956 KB Output is correct
26 Correct 4 ms 1368 KB Output is correct
27 Correct 6 ms 1908 KB Output is correct
28 Correct 238 ms 29880 KB Output is correct
29 Correct 333 ms 39972 KB Output is correct
30 Correct 518 ms 56768 KB Output is correct
31 Correct 633 ms 69228 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 436 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 860 KB Output is correct
44 Correct 4 ms 1052 KB Output is correct
45 Correct 271 ms 32736 KB Output is correct
46 Correct 392 ms 50984 KB Output is correct
47 Correct 383 ms 50956 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 344 KB Output is correct
55 Incorrect 2989 ms 114388 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 242 ms 36804 KB Output is correct
10 Correct 23 ms 3884 KB Output is correct
11 Correct 119 ms 19296 KB Output is correct
12 Correct 31 ms 5432 KB Output is correct
13 Correct 49 ms 10692 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 255 ms 37272 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 436 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 508 ms 58584 KB Output is correct
21 Correct 525 ms 62672 KB Output is correct
22 Correct 534 ms 62348 KB Output is correct
23 Correct 459 ms 67032 KB Output is correct
24 Correct 62 ms 8788 KB Output is correct
25 Correct 363 ms 56748 KB Output is correct
26 Correct 336 ms 56196 KB Output is correct
27 Correct 549 ms 73632 KB Output is correct
28 Correct 549 ms 75144 KB Output is correct
29 Correct 619 ms 73288 KB Output is correct
30 Correct 613 ms 74540 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 33 ms 4796 KB Output is correct
33 Correct 31 ms 5092 KB Output is correct
34 Correct 526 ms 60208 KB Output is correct
35 Correct 17 ms 2680 KB Output is correct
36 Correct 90 ms 15812 KB Output is correct
37 Correct 169 ms 29624 KB Output is correct
38 Correct 218 ms 27204 KB Output is correct
39 Correct 327 ms 33812 KB Output is correct
40 Correct 410 ms 49236 KB Output is correct
41 Correct 506 ms 55412 KB Output is correct
42 Correct 621 ms 63608 KB Output is correct
43 Correct 1 ms 344 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 0 ms 360 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 1 ms 624 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 1 ms 344 KB Output is correct
54 Correct 3 ms 860 KB Output is correct
55 Correct 4 ms 1104 KB Output is correct
56 Correct 306 ms 32156 KB Output is correct
57 Correct 468 ms 52852 KB Output is correct
58 Correct 447 ms 48600 KB Output is correct
59 Correct 0 ms 344 KB Output is correct
60 Correct 0 ms 348 KB Output is correct
61 Correct 0 ms 348 KB Output is correct
62 Correct 562 ms 71776 KB Output is correct
63 Correct 562 ms 74876 KB Output is correct
64 Correct 602 ms 72180 KB Output is correct
65 Correct 5 ms 1240 KB Output is correct
66 Correct 11 ms 2168 KB Output is correct
67 Correct 303 ms 32920 KB Output is correct
68 Correct 474 ms 52108 KB Output is correct
69 Correct 672 ms 66392 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 242 ms 36804 KB Output is correct
10 Correct 23 ms 3884 KB Output is correct
11 Correct 119 ms 19296 KB Output is correct
12 Correct 31 ms 5432 KB Output is correct
13 Correct 49 ms 10692 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 255 ms 37272 KB Output is correct
17 Correct 588 ms 75096 KB Output is correct
18 Correct 561 ms 72500 KB Output is correct
19 Correct 567 ms 61908 KB Output is correct
20 Correct 619 ms 64140 KB Output is correct
21 Correct 557 ms 63760 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 79 ms 10900 KB Output is correct
24 Correct 32 ms 5448 KB Output is correct
25 Correct 125 ms 20240 KB Output is correct
26 Correct 214 ms 37556 KB Output is correct
27 Correct 289 ms 32860 KB Output is correct
28 Correct 361 ms 41176 KB Output is correct
29 Correct 477 ms 54100 KB Output is correct
30 Correct 549 ms 59504 KB Output is correct
31 Correct 634 ms 64360 KB Output is correct
32 Correct 591 ms 69512 KB Output is correct
33 Correct 536 ms 72720 KB Output is correct
34 Correct 7 ms 1652 KB Output is correct
35 Correct 12 ms 2576 KB Output is correct
36 Correct 272 ms 32788 KB Output is correct
37 Correct 446 ms 53056 KB Output is correct
38 Correct 604 ms 66748 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 432 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 242 ms 36804 KB Output is correct
10 Correct 23 ms 3884 KB Output is correct
11 Correct 119 ms 19296 KB Output is correct
12 Correct 31 ms 5432 KB Output is correct
13 Correct 49 ms 10692 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 2 ms 860 KB Output is correct
16 Correct 255 ms 37272 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 344 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 656 ms 68624 KB Output is correct
24 Correct 0 ms 344 KB Output is correct
25 Correct 3 ms 956 KB Output is correct
26 Correct 4 ms 1368 KB Output is correct
27 Correct 6 ms 1908 KB Output is correct
28 Correct 238 ms 29880 KB Output is correct
29 Correct 333 ms 39972 KB Output is correct
30 Correct 518 ms 56768 KB Output is correct
31 Correct 633 ms 69228 KB Output is correct
32 Correct 0 ms 344 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 436 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 2 ms 860 KB Output is correct
44 Correct 4 ms 1052 KB Output is correct
45 Correct 271 ms 32736 KB Output is correct
46 Correct 392 ms 50984 KB Output is correct
47 Correct 383 ms 50956 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 344 KB Output is correct
55 Incorrect 2989 ms 114388 KB Solution announced impossible, but it is possible.
56 Halted 0 ms 0 KB -