oj.uz

Submission #440163

# Submission time Handle Problem Language Result Execution time Memory
440163 2021-07-01T16:34:05 Z DanerZein Fountain Parks (IOI21_parks) C++17
5 / 100
 485 ms 58388 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;
  int id=-1;
  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;
	unionset(a,b);
	G[a].push_back(b);
	G[b].push_back(a);
      }
    }
    for(int j=0;j<oy[i].size();j++){
      if(id==-1){
	id=oy[i][j].second;
      }
      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;
	unionset(a,b);
	G[a].push_back(b);
	G[b].push_back(a);
      }
    }
  }
  if(tam[findset(0)]!=n) return 0;
  queue<int> q; q.push(id);
  set<ii> ban;
  while(!q.empty()){
    int u; u=q.front();
    q.pop();
    vis[u]=1;
    vector<iii> pro;
    for(auto &v:G[u]){
      if(!vis[v]) pro.push_back(iii(v,ii(x[v],y[v])));
    }
    sort(pro.begin(),pro.end(),orden);
    for(int i=0;i<pro.size();i++){
      int a=pro[i].first;
      ru.push_back(a); rv.push_back(u);
      int xi,yi;
      if(x[a]==x[u]){
	xi=x[a]-1; yi=(y[a]+y[u])/2;
	if(ban.find(ii(xi,yi))!=ban.end()){
	  xi=x[a]+1;
	}
	ban.insert(ii(xi,yi));
      }
      else{
	xi=(x[a]+x[u])/2; yi=y[a]-1;
	if(ban.find(ii(xi,yi))!=ban.end()){
	  yi=y[a]+1;
	}
	ban.insert(ii(xi,yi));
      }
      ra.push_back(xi); rb.push_back(yi);
      q.push(a);
    }
  }
  build(ru,rv,ra,rb);
  return 1;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 10 ms 9804 KB Output is correct
3 Correct 8 ms 9900 KB Output is correct
4 Correct 9 ms 9892 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Correct 9 ms 9804 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32296 KB Output is correct
10 Correct 19 ms 12236 KB Output is correct
11 Correct 70 ms 21884 KB Output is correct
12 Correct 25 ms 13260 KB Output is correct
13 Correct 27 ms 15080 KB Output is correct
14 Correct 11 ms 9932 KB Output is correct
15 Correct 11 ms 10060 KB Output is correct
16 Correct 169 ms 32312 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 10 ms 9804 KB Output is correct
3 Correct 8 ms 9900 KB Output is correct
4 Correct 9 ms 9892 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Correct 9 ms 9804 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32296 KB Output is correct
10 Correct 19 ms 12236 KB Output is correct
11 Correct 70 ms 21884 KB Output is correct
12 Correct 25 ms 13260 KB Output is correct
13 Correct 27 ms 15080 KB Output is correct
14 Correct 11 ms 9932 KB Output is correct
15 Correct 11 ms 10060 KB Output is correct
16 Correct 169 ms 32312 KB Output is correct
17 Correct 10 ms 9804 KB Output is correct
18 Correct 8 ms 9804 KB Output is correct
19 Incorrect 8 ms 9804 KB Edge between 0 and 4 appears more than once: appeared on positions 5 and 6
20 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 10 ms 9804 KB Output is correct
3 Correct 8 ms 9900 KB Output is correct
4 Correct 9 ms 9892 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Correct 9 ms 9804 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32296 KB Output is correct
10 Correct 19 ms 12236 KB Output is correct
11 Correct 70 ms 21884 KB Output is correct
12 Correct 25 ms 13260 KB Output is correct
13 Correct 27 ms 15080 KB Output is correct
14 Correct 11 ms 9932 KB Output is correct
15 Correct 11 ms 10060 KB Output is correct
16 Correct 169 ms 32312 KB Output is correct
17 Correct 10 ms 9804 KB Output is correct
18 Correct 8 ms 9804 KB Output is correct
19 Incorrect 8 ms 9804 KB Edge between 0 and 4 appears more than once: appeared on positions 5 and 6
20 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 10 ms 9804 KB Output is correct
3 Correct 8 ms 9900 KB Output is correct
4 Correct 9 ms 9892 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Correct 9 ms 9804 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32296 KB Output is correct
10 Correct 19 ms 12236 KB Output is correct
11 Correct 70 ms 21884 KB Output is correct
12 Correct 25 ms 13260 KB Output is correct
13 Correct 27 ms 15080 KB Output is correct
14 Correct 11 ms 9932 KB Output is correct
15 Correct 11 ms 10060 KB Output is correct
16 Correct 169 ms 32312 KB Output is correct
17 Correct 10 ms 9904 KB Output is correct
18 Correct 8 ms 9804 KB Output is correct
19 Correct 9 ms 9804 KB Output is correct
20 Correct 472 ms 50568 KB Output is correct
21 Correct 436 ms 49360 KB Output is correct
22 Correct 470 ms 49816 KB Output is correct
23 Correct 316 ms 43396 KB Output is correct
24 Correct 83 ms 23236 KB Output is correct
25 Correct 143 ms 29076 KB Output is correct
26 Correct 129 ms 29068 KB Output is correct
27 Correct 375 ms 48024 KB Output is correct
28 Correct 397 ms 47972 KB Output is correct
29 Correct 417 ms 48220 KB Output is correct
30 Correct 419 ms 48036 KB Output is correct
31 Correct 10 ms 9804 KB Output is correct
32 Incorrect 33 ms 13008 KB Tree @(185817, 20263) appears more than once: for edges on positions 108 and 114
33 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 10 ms 9804 KB Output is correct
3 Correct 8 ms 9900 KB Output is correct
4 Correct 9 ms 9892 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Correct 9 ms 9804 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32296 KB Output is correct
10 Correct 19 ms 12236 KB Output is correct
11 Correct 70 ms 21884 KB Output is correct
12 Correct 25 ms 13260 KB Output is correct
13 Correct 27 ms 15080 KB Output is correct
14 Correct 11 ms 9932 KB Output is correct
15 Correct 11 ms 10060 KB Output is correct
16 Correct 169 ms 32312 KB Output is correct
17 Correct 388 ms 48968 KB Output is correct
18 Incorrect 485 ms 58388 KB Edge between 87978 and 183490 appears more than once: appeared on positions 100000 and 100002
19 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9804 KB Output is correct
2 Correct 10 ms 9804 KB Output is correct
3 Correct 8 ms 9900 KB Output is correct
4 Correct 9 ms 9892 KB Output is correct
5 Correct 8 ms 9804 KB Output is correct
6 Correct 9 ms 9804 KB Output is correct
7 Correct 9 ms 9804 KB Output is correct
8 Correct 9 ms 9804 KB Output is correct
9 Correct 175 ms 32296 KB Output is correct
10 Correct 19 ms 12236 KB Output is correct
11 Correct 70 ms 21884 KB Output is correct
12 Correct 25 ms 13260 KB Output is correct
13 Correct 27 ms 15080 KB Output is correct
14 Correct 11 ms 9932 KB Output is correct
15 Correct 11 ms 10060 KB Output is correct
16 Correct 169 ms 32312 KB Output is correct
17 Correct 10 ms 9804 KB Output is correct
18 Correct 8 ms 9804 KB Output is correct
19 Incorrect 8 ms 9804 KB Edge between 0 and 4 appears more than once: appeared on positions 5 and 6
20 Halted 0 ms 0 KB -