oj.uz

Submission #440237

# Submission time Handle Problem Language Result Execution time Memory
440237 2021-07-01T19:29:17 Z DanerZein Fountain Parks (IOI21_parks) C++17
55 / 100
 586 ms 50664 KB 
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int MAX_N=2e5+10;
vector<vi> G;
int pa[MAX_N],tam[MAX_N];
bool vis[MAX_N];
vector<ii> ox[MAX_N],oy[MAX_N];
void init(int n){
  for(int i=0;i<n;i++){
    pa[i]=i; tam[i]=1;
  }
}
int findset(int i){
  if(pa[i]==i) return i;
  return pa[i]=findset(pa[i]);
}
bool issameset(int i,int j){
  return findset(i)==findset(j);
}
void unionset(int i,int j){
  if(!issameset(i,j)){
    int u=findset(i),v=findset(j);
    pa[u]=v;
    tam[v]+=tam[u];
  }
}
bool orden(iii a,iii b){
  if(a.second.second==b.second.second){
    return a.second.first<b.second.first;
  }
  return a.second.second<b.second.second;
}
int construct_roads(std::vector<int> x, std::vector<int> y) {
  int n=x.size();
  G.clear(); G.resize(n+1);
  for(int i=0;i<MAX_N;i++){
    ox[i].clear(); oy[i].clear();
  }
  memset(vis,0,sizeof vis);

  init(n);
  for(int i=0;i<n;i++){
    ox[x[i]].push_back(ii(y[i],i));
    oy[y[i]].push_back(ii(x[i],i));
  }
  for(int i=0;i<MAX_N;i++){
    sort(ox[i].begin(),ox[i].end());
    sort(oy[i].begin(),oy[i].end());
  }
  vector<int> ru,rv,ra,rb;
  for(int i=0;i<MAX_N;i++){
    int a,b;
    for(int j=0;j<ox[i].size();j++){
      if(j+1!=ox[i].size() && ox[i][j+1].first-ox[i][j].first==2){
	a=ox[i][j+1].second; b=ox[i][j].second;
	if(issameset(a,b)) continue;
	unionset(a,b);
	G[a].push_back(b);
	G[b].push_back(a);
      }
    }
    for(int j=0;j<oy[i].size();j++){
      if(j+1!=oy[i].size() && oy[i][j+1].first-oy[i][j].first==2){
	a=oy[i][j+1].second; b=oy[i][j].second;
	if(issameset(a,b)) continue;
	unionset(a,b);
	G[a].push_back(b);
	G[b].push_back(a);
      }
    }
  }
  if(tam[findset(0)]!=n) return 0;
  int id=-1;
  for(int i=0;i<n;i++){
    if(G[i].size()==1){
      id=i; break;
    }
  }
  if(id==-1) id=0;
  queue<int> q; q.push(id);
  set<ii> ban; vis[id]=1;
  while(!q.empty()){
    int u; u=q.front();
    q.pop();
    int c=0;
    for(auto &v:G[u]){
      if(!vis[v]) c++;
    }
    while(c!=0){
      int id=-1;
      for(auto &v:G[u]){
	if(vis[v]) continue;
	id=v;
	int mid;
	if(x[u]==x[v]){
	  mid=(y[u]+y[v])/2;
	  if(ban.find(ii(x[u]+1,mid))!=ban.end() || ban.find(ii(x[u]-1,mid))!=ban.end()){
	    id=v; break;
	  }
	}
	else{
	  mid=(x[u]+x[v])/2;
	  if(ban.find(ii(mid,y[u]+1))!=ban.end() || ban.find(ii(mid,y[u]-1))!=ban.end()){
	    id=v; break;
	  }
	}
      }
      if(id==-1) break;
      vis[id]=1;
      int a,b,mid;
      if(x[u]==x[id]){
	mid=(y[u]+y[id])/2;
	if(ban.find(ii(x[u]-1,mid))==ban.end()){
	  a=x[u]-1; b=mid;
	}
	else{
	  a=x[u]+1; b=mid;
	}
      }
      else{
	mid=(x[u]+x[id])/2;
	if(ban.find(ii(mid,y[u]-1))==ban.end()){
	  a=mid; b=y[u]-1;
	}
	else{
	  a=mid; b=y[u]+1;

	}
      }
      ban.insert(ii(a,b));
      ru.push_back(u); rv.push_back(id);
      ra.push_back(a); rb.push_back(b);
      q.push(id);
      c--;
    }
  }
  build(ru,rv,ra,rb);
  return 1;
}

Compilation message

parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:57: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]
   57 |     for(int j=0;j<ox[i].size();j++){
      |                 ~^~~~~~~~~~~~~
parks.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |       if(j+1!=ox[i].size() && ox[i][j+1].first-ox[i][j].first==2){
      |          ~~~^~~~~~~~~~~~~~
parks.cpp:66: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]
   66 |     for(int j=0;j<oy[i].size();j++){
      |                 ~^~~~~~~~~~~~~
parks.cpp:67:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |       if(j+1!=oy[i].size() && oy[i][j+1].first-oy[i][j].first==2){
      |          ~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 8 ms 9804 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct
4 Correct 7 ms 9804 KB Output is correct
5 Correct 9 ms 9804 KB Output is correct
6 Correct 10 ms 9896 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32332 KB Output is correct
10 Correct 23 ms 12188 KB Output is correct
11 Correct 76 ms 21980 KB Output is correct
12 Correct 28 ms 13284 KB Output is correct
13 Correct 26 ms 15112 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 10 ms 10060 KB Output is correct
16 Correct 173 ms 32332 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 8 ms 9804 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct
4 Correct 7 ms 9804 KB Output is correct
5 Correct 9 ms 9804 KB Output is correct
6 Correct 10 ms 9896 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32332 KB Output is correct
10 Correct 23 ms 12188 KB Output is correct
11 Correct 76 ms 21980 KB Output is correct
12 Correct 28 ms 13284 KB Output is correct
13 Correct 26 ms 15112 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 10 ms 10060 KB Output is correct
16 Correct 173 ms 32332 KB Output is correct
17 Correct 10 ms 9804 KB Output is correct
18 Correct 9 ms 9892 KB Output is correct
19 Correct 9 ms 9804 KB Output is correct
20 Correct 8 ms 9848 KB Output is correct
21 Correct 9 ms 9804 KB Output is correct
22 Correct 9 ms 9804 KB Output is correct
23 Correct 420 ms 49244 KB Output is correct
24 Correct 9 ms 9804 KB Output is correct
25 Correct 11 ms 10060 KB Output is correct
26 Correct 9 ms 10196 KB Output is correct
27 Correct 11 ms 10188 KB Output is correct
28 Correct 132 ms 25804 KB Output is correct
29 Correct 210 ms 33408 KB Output is correct
30 Correct 291 ms 41556 KB Output is correct
31 Correct 401 ms 49216 KB Output is correct
32 Correct 9 ms 9804 KB Output is correct
33 Correct 8 ms 9804 KB Output is correct
34 Correct 9 ms 9824 KB Output is correct
35 Correct 7 ms 9804 KB Output is correct
36 Correct 8 ms 9804 KB Output is correct
37 Correct 9 ms 9804 KB Output is correct
38 Correct 8 ms 9804 KB Output is correct
39 Correct 8 ms 9804 KB Output is correct
40 Correct 8 ms 9804 KB Output is correct
41 Correct 8 ms 9804 KB Output is correct
42 Correct 8 ms 9892 KB Output is correct
43 Correct 8 ms 10060 KB Output is correct
44 Correct 9 ms 10164 KB Output is correct
45 Correct 197 ms 30196 KB Output is correct
46 Correct 313 ms 39980 KB Output is correct
47 Correct 319 ms 40292 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 8 ms 9804 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct
4 Correct 7 ms 9804 KB Output is correct
5 Correct 9 ms 9804 KB Output is correct
6 Correct 10 ms 9896 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32332 KB Output is correct
10 Correct 23 ms 12188 KB Output is correct
11 Correct 76 ms 21980 KB Output is correct
12 Correct 28 ms 13284 KB Output is correct
13 Correct 26 ms 15112 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 10 ms 10060 KB Output is correct
16 Correct 173 ms 32332 KB Output is correct
17 Correct 10 ms 9804 KB Output is correct
18 Correct 9 ms 9892 KB Output is correct
19 Correct 9 ms 9804 KB Output is correct
20 Correct 8 ms 9848 KB Output is correct
21 Correct 9 ms 9804 KB Output is correct
22 Correct 9 ms 9804 KB Output is correct
23 Correct 420 ms 49244 KB Output is correct
24 Correct 9 ms 9804 KB Output is correct
25 Correct 11 ms 10060 KB Output is correct
26 Correct 9 ms 10196 KB Output is correct
27 Correct 11 ms 10188 KB Output is correct
28 Correct 132 ms 25804 KB Output is correct
29 Correct 210 ms 33408 KB Output is correct
30 Correct 291 ms 41556 KB Output is correct
31 Correct 401 ms 49216 KB Output is correct
32 Correct 9 ms 9804 KB Output is correct
33 Correct 8 ms 9804 KB Output is correct
34 Correct 9 ms 9824 KB Output is correct
35 Correct 7 ms 9804 KB Output is correct
36 Correct 8 ms 9804 KB Output is correct
37 Correct 9 ms 9804 KB Output is correct
38 Correct 8 ms 9804 KB Output is correct
39 Correct 8 ms 9804 KB Output is correct
40 Correct 8 ms 9804 KB Output is correct
41 Correct 8 ms 9804 KB Output is correct
42 Correct 8 ms 9892 KB Output is correct
43 Correct 8 ms 10060 KB Output is correct
44 Correct 9 ms 10164 KB Output is correct
45 Correct 197 ms 30196 KB Output is correct
46 Correct 313 ms 39980 KB Output is correct
47 Correct 319 ms 40292 KB Output is correct
48 Correct 8 ms 9804 KB Output is correct
49 Correct 7 ms 9804 KB Output is correct
50 Correct 8 ms 9804 KB Output is correct
51 Correct 10 ms 9984 KB Output is correct
52 Correct 9 ms 9892 KB Output is correct
53 Correct 8 ms 9804 KB Output is correct
54 Correct 8 ms 9804 KB Output is correct
55 Correct 412 ms 49532 KB Output is correct
56 Correct 8 ms 9804 KB Output is correct
57 Incorrect 12 ms 10168 KB Tree @(3, 185601) appears more than once: for edges on positions 587 and 588
58 Halted 0 ms 0 KB -

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 8 ms 9804 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct
4 Correct 7 ms 9804 KB Output is correct
5 Correct 9 ms 9804 KB Output is correct
6 Correct 10 ms 9896 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32332 KB Output is correct
10 Correct 23 ms 12188 KB Output is correct
11 Correct 76 ms 21980 KB Output is correct
12 Correct 28 ms 13284 KB Output is correct
13 Correct 26 ms 15112 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 10 ms 10060 KB Output is correct
16 Correct 173 ms 32332 KB Output is correct
17 Correct 9 ms 9804 KB Output is correct
18 Correct 9 ms 9804 KB Output is correct
19 Correct 7 ms 9804 KB Output is correct
20 Correct 515 ms 50664 KB Output is correct
21 Correct 415 ms 49432 KB Output is correct
22 Correct 458 ms 49836 KB Output is correct
23 Correct 364 ms 43368 KB Output is correct
24 Correct 80 ms 23172 KB Output is correct
25 Correct 158 ms 29180 KB Output is correct
26 Correct 147 ms 29132 KB Output is correct
27 Correct 409 ms 47932 KB Output is correct
28 Correct 452 ms 48004 KB Output is correct
29 Correct 402 ms 48048 KB Output is correct
30 Correct 439 ms 47972 KB Output is correct
31 Correct 9 ms 9804 KB Output is correct
32 Correct 33 ms 12996 KB Output is correct
33 Correct 92 ms 20728 KB Output is correct
34 Correct 586 ms 50524 KB Output is correct
35 Correct 14 ms 10828 KB Output is correct
36 Correct 40 ms 14976 KB Output is correct
37 Correct 85 ms 20036 KB Output is correct
38 Correct 179 ms 25268 KB Output is correct
39 Correct 232 ms 31528 KB Output is correct
40 Correct 307 ms 37384 KB Output is correct
41 Correct 410 ms 43164 KB Output is correct
42 Correct 493 ms 48844 KB Output is correct
43 Correct 9 ms 9804 KB Output is correct
44 Correct 9 ms 9876 KB Output is correct
45 Correct 9 ms 9804 KB Output is correct
46 Correct 8 ms 9796 KB Output is correct
47 Correct 9 ms 9804 KB Output is correct
48 Correct 9 ms 9900 KB Output is correct
49 Correct 8 ms 9804 KB Output is correct
50 Correct 8 ms 9804 KB Output is correct
51 Correct 7 ms 9804 KB Output is correct
52 Correct 8 ms 9804 KB Output is correct
53 Correct 7 ms 9824 KB Output is correct
54 Correct 9 ms 10060 KB Output is correct
55 Correct 10 ms 10188 KB Output is correct
56 Correct 185 ms 30212 KB Output is correct
57 Correct 289 ms 39980 KB Output is correct
58 Correct 283 ms 39980 KB Output is correct
59 Correct 7 ms 9796 KB Output is correct
60 Correct 8 ms 9804 KB Output is correct
61 Correct 8 ms 9804 KB Output is correct
62 Correct 373 ms 49252 KB Output is correct
63 Correct 381 ms 49280 KB Output is correct
64 Correct 397 ms 49148 KB Output is correct
65 Correct 11 ms 10316 KB Output is correct
66 Correct 14 ms 10696 KB Output is correct
67 Correct 209 ms 29728 KB Output is correct
68 Correct 287 ms 39588 KB Output is correct
69 Correct 415 ms 49700 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 8 ms 9804 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct
4 Correct 7 ms 9804 KB Output is correct
5 Correct 9 ms 9804 KB Output is correct
6 Correct 10 ms 9896 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32332 KB Output is correct
10 Correct 23 ms 12188 KB Output is correct
11 Correct 76 ms 21980 KB Output is correct
12 Correct 28 ms 13284 KB Output is correct
13 Correct 26 ms 15112 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 10 ms 10060 KB Output is correct
16 Correct 173 ms 32332 KB Output is correct
17 Correct 370 ms 48984 KB Output is correct
18 Correct 373 ms 49016 KB Output is correct
19 Correct 451 ms 49324 KB Output is correct
20 Correct 404 ms 46744 KB Output is correct
21 Correct 430 ms 44640 KB Output is correct
22 Correct 9 ms 9804 KB Output is correct
23 Correct 66 ms 16248 KB Output is correct
24 Correct 20 ms 11924 KB Output is correct
25 Correct 52 ms 16908 KB Output is correct
26 Correct 89 ms 22036 KB Output is correct
27 Correct 221 ms 29480 KB Output is correct
28 Correct 246 ms 34500 KB Output is correct
29 Correct 317 ms 39320 KB Output is correct
30 Correct 399 ms 43928 KB Output is correct
31 Correct 497 ms 48664 KB Output is correct
32 Correct 436 ms 49320 KB Output is correct
33 Correct 367 ms 49260 KB Output is correct
34 Correct 11 ms 10424 KB Output is correct
35 Correct 13 ms 10792 KB Output is correct
36 Correct 193 ms 29624 KB Output is correct
37 Correct 316 ms 39508 KB Output is correct
38 Correct 433 ms 49724 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 8 ms 9804 KB Output is correct
3 Correct 7 ms 9804 KB Output is correct
4 Correct 7 ms 9804 KB Output is correct
5 Correct 9 ms 9804 KB Output is correct
6 Correct 10 ms 9896 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32332 KB Output is correct
10 Correct 23 ms 12188 KB Output is correct
11 Correct 76 ms 21980 KB Output is correct
12 Correct 28 ms 13284 KB Output is correct
13 Correct 26 ms 15112 KB Output is correct
14 Correct 8 ms 9932 KB Output is correct
15 Correct 10 ms 10060 KB Output is correct
16 Correct 173 ms 32332 KB Output is correct
17 Correct 10 ms 9804 KB Output is correct
18 Correct 9 ms 9892 KB Output is correct
19 Correct 9 ms 9804 KB Output is correct
20 Correct 8 ms 9848 KB Output is correct
21 Correct 9 ms 9804 KB Output is correct
22 Correct 9 ms 9804 KB Output is correct
23 Correct 420 ms 49244 KB Output is correct
24 Correct 9 ms 9804 KB Output is correct
25 Correct 11 ms 10060 KB Output is correct
26 Correct 9 ms 10196 KB Output is correct
27 Correct 11 ms 10188 KB Output is correct
28 Correct 132 ms 25804 KB Output is correct
29 Correct 210 ms 33408 KB Output is correct
30 Correct 291 ms 41556 KB Output is correct
31 Correct 401 ms 49216 KB Output is correct
32 Correct 9 ms 9804 KB Output is correct
33 Correct 8 ms 9804 KB Output is correct
34 Correct 9 ms 9824 KB Output is correct
35 Correct 7 ms 9804 KB Output is correct
36 Correct 8 ms 9804 KB Output is correct
37 Correct 9 ms 9804 KB Output is correct
38 Correct 8 ms 9804 KB Output is correct
39 Correct 8 ms 9804 KB Output is correct
40 Correct 8 ms 9804 KB Output is correct
41 Correct 8 ms 9804 KB Output is correct
42 Correct 8 ms 9892 KB Output is correct
43 Correct 8 ms 10060 KB Output is correct
44 Correct 9 ms 10164 KB Output is correct
45 Correct 197 ms 30196 KB Output is correct
46 Correct 313 ms 39980 KB Output is correct
47 Correct 319 ms 40292 KB Output is correct
48 Correct 8 ms 9804 KB Output is correct
49 Correct 7 ms 9804 KB Output is correct
50 Correct 8 ms 9804 KB Output is correct
51 Correct 10 ms 9984 KB Output is correct
52 Correct 9 ms 9892 KB Output is correct
53 Correct 8 ms 9804 KB Output is correct
54 Correct 8 ms 9804 KB Output is correct
55 Correct 412 ms 49532 KB Output is correct
56 Correct 8 ms 9804 KB Output is correct
57 Incorrect 12 ms 10168 KB Tree @(3, 185601) appears more than once: for edges on positions 587 and 588
58 Halted 0 ms 0 KB -