oj.uz

Submission #443452

# Submission time Handle Problem Language Result Execution time Memory
443452 2021-07-10T14:06:20 Z leinad2 Fountain Parks (IOI21_parks) C++17
55 / 100
 2462 ms 107712 KB 
#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
int par[400010], chk[400010], chk2[400010], A[400010][2], vis[400010];
int Find(int v){return v==par[v]?v:par[v]=Find(par[v]);}
vector<pair<int, int> >v;
int cnt;
map<pair<int, int>, int>mp;
vector<pair<int, int> >adj[400010];
vector<int>_u, _v, _a, _b;
void dfs(int v)
{
    for(int i=0;i<adj[v].size();i++)
    {
        int p=adj[v][i].first;
        if(!vis[p])vis[p]=1,dfs(p),_a[adj[v][i].second]=p;
    }
}
int construct_roads(vector<int>x, vector<int>y)
{
    int n, i, j, k, a, b;
    n=x.size();
    vector<pair<pair<int, int>, int> >V;
    for(i=0;i<n;i++)
    {
        V.push_back({{x[i], y[i]}, i});
    }
    sort(V.begin(), V.end());
    for(i=1;i<V.size();i++)
    {
        if(V[i].first.first==V[i-1].first.first&&V[i].first.second==V[i-1].first.second+2)
        {
            v.push_back({V[i].second, V[i-1].second});
        }
    }
    for(i=0;i<n;i++)
    {
        swap(V[i].first.first, V[i].first.second);
    }
    sort(V.begin(), V.end());
    for(i=1;i<V.size();i++)
    {
        if(V[i].first.first==V[i-1].first.first&&V[i].first.second==V[i-1].first.second+2)
        {
            v.push_back({V[i].second, V[i-1].second});
        }
    }
    for(int rng=0;rng<5;rng++)
    {
        for(i=0;i<n;i++)par[i]=i;
        random_shuffle(v.begin(), v.end());
        _u.clear();_v.clear();_a.clear();_b.clear();cnt=0;mp.clear();for(i=1;i<=2*n;i++)vis[i]=chk[i]=chk2[i]=0,adj[i].clear();
        for(i=0;i<v.size();i++)
        {
            if(Find(v[i].first)!=Find(v[i].second))
            {
                _u.push_back(v[i].first);
                _v.push_back(v[i].second);
                par[Find(v[i].first)]=Find(v[i].second);
            }
        }
        if(_u.size()!=n-1)return 0;
        vector<pair<int, int> >edge;
        _a.resize(n-1);_b.resize(n-1);
        for(i=0;i<_u.size();i++)
        {
            int a=_u[i], b=_v[i], q, w, e, r;
            if(x[a]==x[b])
            {
                q=x[a]-1;e=x[a]+1;
                w=r=(y[a]+y[b])/2;
            }
            else
            {
                w=y[a]-1;r=y[a]+1;
                q=e=(x[a]+x[b])/2;
            }
            if(mp.find({q, w})==mp.end())mp[{q, w}]=++cnt,A[cnt][0]=q,A[cnt][1]=w;
            if(mp.find({e, r})==mp.end())mp[{e, r}]=++cnt,A[cnt][0]=e,A[cnt][1]=r;
            int x=mp[{q, w}];int y=mp[{e, r}];
            edge.push_back({x, y});
        }
        for(i=0;i++<cnt;)par[i]=i;
        for(i=0;i<edge.size();i++)par[Find(edge[i].first)]=Find(edge[i].second);
        for(i=0;i++<cnt;)chk[Find(i)]++;
        for(i=0;i<edge.size();i++)chk2[Find(edge[i].first)]++;
        for(i=0;i<edge.size();i++)
        {
            adj[edge[i].first].push_back({edge[i].second, i});
            adj[edge[i].second].push_back({edge[i].first, i});
        }
        bool flag=true;
        for(i=0;i++<cnt;)
        {
            if(chk[i])
            {
                if(chk[i]<chk2[i]){flag=false;break;}
                else vis[i]=1,dfs(i);
            }
        }
        if(!flag)continue;
        for(i=0;i<_a.size();i++)
        {
            if(_a[i]==0)_a[i]=Find(edge[i].first);
            int a=_a[i];
            _a[i]=A[a][0];_b[i]=A[a][1];
        }
        build(_u, _v, _a, _b);
        return 1;
    }
}

Compilation message

parks.cpp: In function 'void dfs(int)':
parks.cpp:13:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     for(int i=0;i<adj[v].size();i++)
      |                 ~^~~~~~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:29:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(i=1;i<V.size();i++)
      |             ~^~~~~~~~~
parks.cpp:41:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(i=1;i<V.size();i++)
      |             ~^~~~~~~~~
parks.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |         for(i=0;i<v.size();i++)
      |                 ~^~~~~~~~~
parks.cpp:62:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |         if(_u.size()!=n-1)return 0;
      |            ~~~~~~~~~^~~~~
parks.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(i=0;i<_u.size();i++)
      |                 ~^~~~~~~~~~
parks.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         for(i=0;i<edge.size();i++)par[Find(edge[i].first)]=Find(edge[i].second);
      |                 ~^~~~~~~~~~~~
parks.cpp:86:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for(i=0;i<edge.size();i++)chk2[Find(edge[i].first)]++;
      |                 ~^~~~~~~~~~~~
parks.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for(i=0;i<edge.size();i++)
      |                 ~^~~~~~~~~~~~
parks.cpp:102:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         for(i=0;i<_a.size();i++)
      |                 ~^~~~~~~~~~
parks.cpp:21:15: warning: unused variable 'j' [-Wunused-variable]
   21 |     int n, i, j, k, a, b;
      |               ^
parks.cpp:21:18: warning: unused variable 'k' [-Wunused-variable]
   21 |     int n, i, j, k, a, b;
      |                  ^
parks.cpp:21:21: warning: unused variable 'a' [-Wunused-variable]
   21 |     int n, i, j, k, a, b;
      |                     ^
parks.cpp:21:24: warning: unused variable 'b' [-Wunused-variable]
   21 |     int n, i, j, k, a, b;
      |                        ^
parks.cpp:23:39: warning: control reaches end of non-void function [-Wreturn-type]
   23 |     vector<pair<pair<int, int>, int> >V;
      |                                       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 335 ms 42384 KB Output is correct
10 Correct 25 ms 12944 KB Output is correct
11 Correct 124 ms 27136 KB Output is correct
12 Correct 35 ms 14572 KB Output is correct
13 Correct 21 ms 13108 KB Output is correct
14 Correct 8 ms 9676 KB Output is correct
15 Correct 7 ms 9872 KB Output is correct
16 Correct 253 ms 42300 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 335 ms 42384 KB Output is correct
10 Correct 25 ms 12944 KB Output is correct
11 Correct 124 ms 27136 KB Output is correct
12 Correct 35 ms 14572 KB Output is correct
13 Correct 21 ms 13108 KB Output is correct
14 Correct 8 ms 9676 KB Output is correct
15 Correct 7 ms 9872 KB Output is correct
16 Correct 253 ms 42300 KB Output is correct
17 Correct 7 ms 9676 KB Output is correct
18 Correct 8 ms 9676 KB Output is correct
19 Correct 7 ms 9676 KB Output is correct
20 Correct 6 ms 9676 KB Output is correct
21 Correct 7 ms 9676 KB Output is correct
22 Correct 6 ms 9676 KB Output is correct
23 Correct 658 ms 59968 KB Output is correct
24 Correct 6 ms 9676 KB Output is correct
25 Correct 8 ms 9932 KB Output is correct
26 Correct 8 ms 9932 KB Output is correct
27 Correct 8 ms 9988 KB Output is correct
28 Correct 195 ms 29776 KB Output is correct
29 Correct 347 ms 39752 KB Output is correct
30 Correct 509 ms 49528 KB Output is correct
31 Correct 685 ms 59752 KB Output is correct
32 Correct 6 ms 9676 KB Output is correct
33 Correct 7 ms 9676 KB Output is correct
34 Correct 8 ms 9676 KB Output is correct
35 Correct 6 ms 9676 KB Output is correct
36 Correct 7 ms 9648 KB Output is correct
37 Correct 6 ms 9676 KB Output is correct
38 Correct 6 ms 9676 KB Output is correct
39 Correct 7 ms 9676 KB Output is correct
40 Correct 6 ms 9676 KB Output is correct
41 Correct 7 ms 9676 KB Output is correct
42 Correct 7 ms 9676 KB Output is correct
43 Correct 8 ms 9804 KB Output is correct
44 Correct 8 ms 9932 KB Output is correct
45 Correct 274 ms 35688 KB Output is correct
46 Correct 512 ms 47348 KB Output is correct
47 Correct 487 ms 47384 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 335 ms 42384 KB Output is correct
10 Correct 25 ms 12944 KB Output is correct
11 Correct 124 ms 27136 KB Output is correct
12 Correct 35 ms 14572 KB Output is correct
13 Correct 21 ms 13108 KB Output is correct
14 Correct 8 ms 9676 KB Output is correct
15 Correct 7 ms 9872 KB Output is correct
16 Correct 253 ms 42300 KB Output is correct
17 Correct 7 ms 9676 KB Output is correct
18 Correct 8 ms 9676 KB Output is correct
19 Correct 7 ms 9676 KB Output is correct
20 Correct 6 ms 9676 KB Output is correct
21 Correct 7 ms 9676 KB Output is correct
22 Correct 6 ms 9676 KB Output is correct
23 Correct 658 ms 59968 KB Output is correct
24 Correct 6 ms 9676 KB Output is correct
25 Correct 8 ms 9932 KB Output is correct
26 Correct 8 ms 9932 KB Output is correct
27 Correct 8 ms 9988 KB Output is correct
28 Correct 195 ms 29776 KB Output is correct
29 Correct 347 ms 39752 KB Output is correct
30 Correct 509 ms 49528 KB Output is correct
31 Correct 685 ms 59752 KB Output is correct
32 Correct 6 ms 9676 KB Output is correct
33 Correct 7 ms 9676 KB Output is correct
34 Correct 8 ms 9676 KB Output is correct
35 Correct 6 ms 9676 KB Output is correct
36 Correct 7 ms 9648 KB Output is correct
37 Correct 6 ms 9676 KB Output is correct
38 Correct 6 ms 9676 KB Output is correct
39 Correct 7 ms 9676 KB Output is correct
40 Correct 6 ms 9676 KB Output is correct
41 Correct 7 ms 9676 KB Output is correct
42 Correct 7 ms 9676 KB Output is correct
43 Correct 8 ms 9804 KB Output is correct
44 Correct 8 ms 9932 KB Output is correct
45 Correct 274 ms 35688 KB Output is correct
46 Correct 512 ms 47348 KB Output is correct
47 Correct 487 ms 47384 KB Output is correct
48 Correct 6 ms 9676 KB Output is correct
49 Correct 7 ms 9676 KB Output is correct
50 Correct 8 ms 9676 KB Output is correct
51 Correct 8 ms 9676 KB Output is correct
52 Correct 6 ms 9676 KB Output is correct
53 Correct 7 ms 9676 KB Output is correct
54 Correct 7 ms 9676 KB Output is correct
55 Runtime error 2462 ms 107712 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 335 ms 42384 KB Output is correct
10 Correct 25 ms 12944 KB Output is correct
11 Correct 124 ms 27136 KB Output is correct
12 Correct 35 ms 14572 KB Output is correct
13 Correct 21 ms 13108 KB Output is correct
14 Correct 8 ms 9676 KB Output is correct
15 Correct 7 ms 9872 KB Output is correct
16 Correct 253 ms 42300 KB Output is correct
17 Correct 6 ms 9676 KB Output is correct
18 Correct 7 ms 9676 KB Output is correct
19 Correct 6 ms 9676 KB Output is correct
20 Correct 609 ms 60684 KB Output is correct
21 Correct 600 ms 58184 KB Output is correct
22 Correct 634 ms 57920 KB Output is correct
23 Correct 490 ms 64920 KB Output is correct
24 Correct 97 ms 20792 KB Output is correct
25 Correct 123 ms 25116 KB Output is correct
26 Correct 109 ms 25080 KB Output is correct
27 Correct 643 ms 74612 KB Output is correct
28 Correct 632 ms 74552 KB Output is correct
29 Correct 589 ms 74528 KB Output is correct
30 Correct 637 ms 74568 KB Output is correct
31 Correct 6 ms 9676 KB Output is correct
32 Correct 43 ms 13292 KB Output is correct
33 Correct 48 ms 15248 KB Output is correct
34 Correct 615 ms 62964 KB Output is correct
35 Correct 14 ms 10512 KB Output is correct
36 Correct 41 ms 13528 KB Output is correct
37 Correct 67 ms 17128 KB Output is correct
38 Correct 212 ms 28984 KB Output is correct
39 Correct 338 ms 36000 KB Output is correct
40 Correct 470 ms 43368 KB Output is correct
41 Correct 551 ms 50352 KB Output is correct
42 Correct 681 ms 57524 KB Output is correct
43 Correct 7 ms 9676 KB Output is correct
44 Correct 6 ms 9676 KB Output is correct
45 Correct 6 ms 9676 KB Output is correct
46 Correct 7 ms 9676 KB Output is correct
47 Correct 6 ms 9676 KB Output is correct
48 Correct 6 ms 9640 KB Output is correct
49 Correct 6 ms 9676 KB Output is correct
50 Correct 7 ms 9676 KB Output is correct
51 Correct 6 ms 9676 KB Output is correct
52 Correct 7 ms 9676 KB Output is correct
53 Correct 6 ms 9676 KB Output is correct
54 Correct 7 ms 9804 KB Output is correct
55 Correct 8 ms 9932 KB Output is correct
56 Correct 283 ms 35692 KB Output is correct
57 Correct 431 ms 47372 KB Output is correct
58 Correct 445 ms 47476 KB Output is correct
59 Correct 6 ms 9676 KB Output is correct
60 Correct 6 ms 9676 KB Output is correct
61 Correct 7 ms 9676 KB Output is correct
62 Correct 599 ms 74672 KB Output is correct
63 Correct 639 ms 74548 KB Output is correct
64 Correct 616 ms 74296 KB Output is correct
65 Correct 8 ms 9932 KB Output is correct
66 Correct 10 ms 10188 KB Output is correct
67 Correct 259 ms 35176 KB Output is correct
68 Correct 432 ms 47800 KB Output is correct
69 Correct 622 ms 60536 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 335 ms 42384 KB Output is correct
10 Correct 25 ms 12944 KB Output is correct
11 Correct 124 ms 27136 KB Output is correct
12 Correct 35 ms 14572 KB Output is correct
13 Correct 21 ms 13108 KB Output is correct
14 Correct 8 ms 9676 KB Output is correct
15 Correct 7 ms 9872 KB Output is correct
16 Correct 253 ms 42300 KB Output is correct
17 Correct 608 ms 74604 KB Output is correct
18 Correct 631 ms 74552 KB Output is correct
19 Correct 606 ms 62904 KB Output is correct
20 Correct 657 ms 58656 KB Output is correct
21 Correct 569 ms 60176 KB Output is correct
22 Correct 6 ms 9676 KB Output is correct
23 Correct 73 ms 17780 KB Output is correct
24 Correct 17 ms 11272 KB Output is correct
25 Correct 47 ms 15232 KB Output is correct
26 Correct 74 ms 18616 KB Output is correct
27 Correct 313 ms 34728 KB Output is correct
28 Correct 409 ms 41420 KB Output is correct
29 Correct 480 ms 46808 KB Output is correct
30 Correct 586 ms 52948 KB Output is correct
31 Correct 673 ms 59112 KB Output is correct
32 Correct 658 ms 63600 KB Output is correct
33 Correct 598 ms 74624 KB Output is correct
34 Correct 9 ms 10060 KB Output is correct
35 Correct 14 ms 10472 KB Output is correct
36 Correct 287 ms 35556 KB Output is correct
37 Correct 455 ms 48568 KB Output is correct
38 Correct 682 ms 61304 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9676 KB Output is correct
2 Correct 6 ms 9676 KB Output is correct
3 Correct 6 ms 9676 KB Output is correct
4 Correct 6 ms 9676 KB Output is correct
5 Correct 6 ms 9676 KB Output is correct
6 Correct 6 ms 9676 KB Output is correct
7 Correct 6 ms 9676 KB Output is correct
8 Correct 6 ms 9676 KB Output is correct
9 Correct 335 ms 42384 KB Output is correct
10 Correct 25 ms 12944 KB Output is correct
11 Correct 124 ms 27136 KB Output is correct
12 Correct 35 ms 14572 KB Output is correct
13 Correct 21 ms 13108 KB Output is correct
14 Correct 8 ms 9676 KB Output is correct
15 Correct 7 ms 9872 KB Output is correct
16 Correct 253 ms 42300 KB Output is correct
17 Correct 7 ms 9676 KB Output is correct
18 Correct 8 ms 9676 KB Output is correct
19 Correct 7 ms 9676 KB Output is correct
20 Correct 6 ms 9676 KB Output is correct
21 Correct 7 ms 9676 KB Output is correct
22 Correct 6 ms 9676 KB Output is correct
23 Correct 658 ms 59968 KB Output is correct
24 Correct 6 ms 9676 KB Output is correct
25 Correct 8 ms 9932 KB Output is correct
26 Correct 8 ms 9932 KB Output is correct
27 Correct 8 ms 9988 KB Output is correct
28 Correct 195 ms 29776 KB Output is correct
29 Correct 347 ms 39752 KB Output is correct
30 Correct 509 ms 49528 KB Output is correct
31 Correct 685 ms 59752 KB Output is correct
32 Correct 6 ms 9676 KB Output is correct
33 Correct 7 ms 9676 KB Output is correct
34 Correct 8 ms 9676 KB Output is correct
35 Correct 6 ms 9676 KB Output is correct
36 Correct 7 ms 9648 KB Output is correct
37 Correct 6 ms 9676 KB Output is correct
38 Correct 6 ms 9676 KB Output is correct
39 Correct 7 ms 9676 KB Output is correct
40 Correct 6 ms 9676 KB Output is correct
41 Correct 7 ms 9676 KB Output is correct
42 Correct 7 ms 9676 KB Output is correct
43 Correct 8 ms 9804 KB Output is correct
44 Correct 8 ms 9932 KB Output is correct
45 Correct 274 ms 35688 KB Output is correct
46 Correct 512 ms 47348 KB Output is correct
47 Correct 487 ms 47384 KB Output is correct
48 Correct 6 ms 9676 KB Output is correct
49 Correct 7 ms 9676 KB Output is correct
50 Correct 8 ms 9676 KB Output is correct
51 Correct 8 ms 9676 KB Output is correct
52 Correct 6 ms 9676 KB Output is correct
53 Correct 7 ms 9676 KB Output is correct
54 Correct 7 ms 9676 KB Output is correct
55 Runtime error 2462 ms 107712 KB Execution killed with signal 11
56 Halted 0 ms 0 KB -