Submission #1111694

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
1111694	2024-11-12 16:39:24	siewjh	Fountain Parks (IOI21_parks)	C++17	100 / 100	448 ms	48188 KiB

parks

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
map<pair<int, int>, int> ctid;
set<pair<int, int>> bs;
vector<int> re1, re2, rbx, rby;
int par[MAXN], rnk[MAXN];
int root(int x){
  if (par[x] == -1) return x;
  else return par[x] = root(par[x]);
}
void join(int ra, int rb){
  if (rnk[ra] > rnk[rb]) swap(ra, rb);
  par[ra] = rb;
  if (rnk[ra] == rnk[rb]) rnk[rb]++;
}
bool check(int bx, int by, int n0x, int n0y, int n1x, int n1y){
  if (!ctid.count({n0x, n0y}) || !ctid.count({n1x, n1y})) return 0;
  int n0id = ctid[{n0x, n0y}], n1id = ctid[{n1x, n1y}];
  int r0 = root(n0id), r1 = root(n1id);
  if (r0 == r1) return 0;
  join(r0, r1);
  re1.push_back(n0id); re2.push_back(n1id); rbx.push_back(bx); rby.push_back(by);
  return 1;
}
int construct_roads(vector<int> xv, vector<int> yv) {
  memset(par, -1, sizeof(par));
  int nodes = xv.size();
  for (int i = 0; i < nodes; i++) ctid[{xv[i], yv[i]}] = i;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

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

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30