oj.uz

Submission #722185

# Submission time Handle Problem Language Result Execution time Memory
722185 2023-04-11T14:03:01 Z urosk Fountain Parks (IOI21_parks) C++17
25 / 100
 1186 ms 79624 KB 
#include "parks.h"
#define here cerr<<"==============================\n"
#include <bits/stdc++.h>
#define ll int
#define pll pair<ll,ll>
#define fi first
#define sc second
#define pb push_back
using namespace std;
#define maxn 200005
ll n;
pll a[maxn];
map<pll,ll> mp;
map<pll,ll> id;
vector<ll> dx = {0,0,-2,2};
vector<ll> dy = {-2,2,0,0};
ll sz[maxn];
ll dsu[maxn];
ll col[maxn];
ll tsz = 1;
bool ok = 1;
ll root(ll x){
    while(x!=dsu[x]){
        x = dsu[x];
    }
    return x;
}
ll getcol(ll x){
    ll ans = col[x];
    while(x!=dsu[x]){
        x = dsu[x];
        ans^=col[x];
    }
    return ans;
}
void upd(ll i,ll j,ll e){
    e^=getcol(i)^getcol(j);
    i = root(i);
    j = root(j);
    if(i==j){
        if(e) ok = 0;
        return;
    }
    if(sz[j]>sz[i]) swap(i,j);
    sz[i]+=sz[j];
    dsu[j] = i;
    col[j]^=e;
}
int construct_roads(vector<int> X, vector<int> Y) {
    n = X.size();
    for(ll i = 1;i<=n;i++) a[i] = {X[i-1],Y[i-1]};
    for(ll i = 1;i<=n;i++) mp[a[i]] = i;
    iota(dsu+1,dsu+1+n,1);
    fill(sz+1,sz+1+n,1);
    vector<ll> c,d;
    for(ll i = 1;i<=n;i++){
        ll x = a[i].fi,y = a[i].sc;
        vector<ll> v;
        for(ll e = 0;e<=3;e++){
            ll nx = x + dx[e];
            ll ny = y + dy[e];
            ll j = mp[{nx,ny}];
            v.pb(j);
            if(j&&!id[{i,j}]){
                c.pb(i);
                d.pb(j);
                id[{i,j}] = id[{j,i}] = ++tsz;
            }
        }
        if(v[1]&&v[3]) upd(id[{i,v[1]}],id[{i,v[3]}],1);
        if(v[0]&&v[2]) upd(id[{i,v[0]}],id[{i,v[2]}],1);
        if(v[1]&&v[2]) upd(id[{i,v[1]}],id[{i,v[2]}],0);
        if(v[0]&&v[3]) upd(id[{i,v[0]}],id[{i,v[3]}],0);
    }
    if(!ok) return 0;
    if(c.size()<n-1) return 0;
    vector<pll> ans;
    for(ll i = 0;i<n-1;i++){
        ll x = c[i];
        ll y = d[i];
        ll j = id[{x,y}];
        ll f = getcol(j);
        if(a[x].fi==a[y].fi){
            if(f) ans.pb({a[x].fi+1,(a[x].sc+a[y].sc)/2});
            else ans.pb({a[x].fi-1,(a[x].sc+a[y].sc)/2});
        }else{
            if(f) ans.pb({(a[x].fi+a[y].fi)/2,a[y].sc+1});
            else ans.pb({(a[x].fi+a[y].fi)/2,a[y].sc-1});
        }
    }
    vector<ll> ansx,ansy;
    for(pll p : ans){
        ansx.pb(p.fi);
        ansy.pb(p.sc);
    }
    for(ll i = 0;i<n-1;i++){
        c[i]--;
        d[i]--;
    }
    build(c,d,ansx,ansy);
    return 1;
}
/**
5
4 4
4 6
6 4
4 2
2 4
**/

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:76:16: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   76 |     if(c.size()<n-1) return 0;
      |        ~~~~~~~~^~~~

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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 457 ms 41448 KB Output is correct
10 Correct 20 ms 4484 KB Output is correct
11 Correct 138 ms 22316 KB Output is correct
12 Correct 33 ms 6740 KB Output is correct
13 Correct 92 ms 16240 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 450 ms 41548 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 457 ms 41448 KB Output is correct
10 Correct 20 ms 4484 KB Output is correct
11 Correct 138 ms 22316 KB Output is correct
12 Correct 33 ms 6740 KB Output is correct
13 Correct 92 ms 16240 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 450 ms 41548 KB Output is correct
17 Incorrect 1 ms 212 KB Wrong answer detected in grader
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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 457 ms 41448 KB Output is correct
10 Correct 20 ms 4484 KB Output is correct
11 Correct 138 ms 22316 KB Output is correct
12 Correct 33 ms 6740 KB Output is correct
13 Correct 92 ms 16240 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 450 ms 41548 KB Output is correct
17 Incorrect 1 ms 212 KB Wrong answer detected in grader
18 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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 457 ms 41448 KB Output is correct
10 Correct 20 ms 4484 KB Output is correct
11 Correct 138 ms 22316 KB Output is correct
12 Correct 33 ms 6740 KB Output is correct
13 Correct 92 ms 16240 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 450 ms 41548 KB Output is correct
17 Correct 1 ms 312 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 1140 ms 71972 KB Output is correct
21 Correct 1033 ms 71636 KB Output is correct
22 Correct 1118 ms 71744 KB Output is correct
23 Correct 849 ms 70088 KB Output is correct
24 Correct 748 ms 45840 KB Output is correct
25 Correct 1008 ms 60016 KB Output is correct
26 Correct 1044 ms 59912 KB Output is correct
27 Correct 1180 ms 70720 KB Output is correct
28 Correct 1186 ms 70580 KB Output is correct
29 Correct 1174 ms 70740 KB Output is correct
30 Correct 1107 ms 70684 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 42 ms 5724 KB Output is correct
33 Correct 186 ms 23468 KB Output is correct
34 Correct 994 ms 72072 KB Output is correct
35 Correct 21 ms 3156 KB Output is correct
36 Correct 179 ms 14604 KB Output is correct
37 Correct 413 ms 29084 KB Output is correct
38 Correct 349 ms 27452 KB Output is correct
39 Correct 564 ms 37488 KB Output is correct
40 Correct 777 ms 47688 KB Output is correct
41 Correct 932 ms 57272 KB Output is correct
42 Correct 1143 ms 68024 KB Output is correct
43 Correct 0 ms 312 KB Output is correct
44 Correct 1 ms 312 KB Output is correct
45 Correct 1 ms 212 KB Output is correct
46 Correct 1 ms 212 KB Output is correct
47 Correct 1 ms 212 KB Output is correct
48 Correct 1 ms 212 KB Output is correct
49 Correct 1 ms 212 KB Output is correct
50 Correct 1 ms 308 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 1 ms 312 KB Output is correct
54 Correct 4 ms 852 KB Output is correct
55 Correct 6 ms 1260 KB Output is correct
56 Correct 479 ms 37956 KB Output is correct
57 Correct 783 ms 54508 KB Output is correct
58 Correct 773 ms 54676 KB Output is correct
59 Correct 1 ms 212 KB Output is correct
60 Correct 1 ms 212 KB Output is correct
61 Correct 1 ms 212 KB Output is correct
62 Correct 1073 ms 76160 KB Output is correct
63 Correct 1081 ms 76224 KB Output is correct
64 Correct 1035 ms 75716 KB Output is correct
65 Correct 8 ms 1492 KB Output is correct
66 Correct 17 ms 2752 KB Output is correct
67 Correct 479 ms 36560 KB Output is correct
68 Correct 784 ms 54292 KB Output is correct
69 Correct 1153 ms 72712 KB Output is correct

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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 457 ms 41448 KB Output is correct
10 Correct 20 ms 4484 KB Output is correct
11 Correct 138 ms 22316 KB Output is correct
12 Correct 33 ms 6740 KB Output is correct
13 Correct 92 ms 16240 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 450 ms 41548 KB Output is correct
17 Incorrect 966 ms 79624 KB Wrong answer detected in grader
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 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 457 ms 41448 KB Output is correct
10 Correct 20 ms 4484 KB Output is correct
11 Correct 138 ms 22316 KB Output is correct
12 Correct 33 ms 6740 KB Output is correct
13 Correct 92 ms 16240 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 5 ms 980 KB Output is correct
16 Correct 450 ms 41548 KB Output is correct
17 Incorrect 1 ms 212 KB Wrong answer detected in grader
18 Halted 0 ms 0 KB -