Submission #574132

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
574132	2022-06-08 01:54:39	eecs	Stranded Far From Home (BOI22_island)	C++17	100 / 100	320 ms	30880 KiB

island

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 <bits/stdc++.h>
using namespace std;
const int maxn = 200010;
int n, m, a[maxn], fa[maxn], sum[maxn];
bool vis[maxn], ans[maxn];
vector<int> G[maxn], Q[maxn];
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    vector<array<int, 2>> V;
    for (int i = 1; i <= n; i++) {
        cin >> a[i], V.push_back({a[i], i});
    }
    while (m--) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v), G[v].push_back(u);
    }
    sort(V.begin(), V.end());
    for (int i = 1; i <= n; i++) {
        int j = lower_bound(V.begin(), V.end(), array<int, 2>{a[i] + 1, 0}) - V.begin() - 1;
        Q[j].push_back(i);
    }
    iota(fa + 1, fa + n + 1, 1);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

island.cpp: In function 'int main()':
island.cpp:33:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for (int i = 0; i < V.size(); i++) {
      |                     ~~^~~~~~~~~~
island.cpp:39:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if (i + 1 < V.size() && V[i][0] == V[i + 1][0]) continue;
      |             ~~~~~~^~~~~~~~~~
island.cpp:43:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |             else if (i + 1 == V.size()) ans[x] = 1;
      |                      ~~~~~~^~~~~~~~~~~
island.cpp:32:9: warning: unused variable 'lst' [-Wunused-variable]
   32 |     int lst = 0;
      |         ^~~

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