Submission #435621

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
435621	2021-06-23 13:35:50	prvocislo	Fountain Parks (IOI21_parks)	C++17	100 / 100	1632 ms	65476 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 = 2e5 + 5;
vector<vector<int> > g(maxn);
vector<int> sz(maxn, 0);
int dfs(int u)
{
    sz[u] = 1;
    for (int v : g[u]) if (!sz[v]) sz[u] += dfs(v);
    return sz[u];
}
int construct_roads(vector<int> x, vector<int> y)
{
    map<pair<int, int>, int> m;
    int n = x.size();
    for (int i = 0; i < n; i++)
        m[{x[i], y[i]}] = i;
    set<pair<int, int> > s;
    for (int i = 0; i < n; i++)
    {
        if (m.count({x[i], y[i] + 2}))
        {
            int j = m[{x[i], y[i]+2}];
            g[i].push_back(j), g[j].push_back(i);
            s.insert({x[i]+1, y[i]+1}), s.insert({x[i]-1, y[i]+1});
        }
        if (m.count({x[i] + 2, y[i]}))
        {
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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