oj.uz

Submission #151636

# Submission time Handle Problem Language Result Execution time Memory
151636 2019-09-04T00:48:17 Z kuroni Trip to the Galapagos Islands (FXCUP4_island) C++17
100 / 100
 3380 ms 32844 KB 
#include "island.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 100005;

int m, dsu[N];
map<pair<int, int>, int> ma;
vector<int> col[N];
vector<pair<int, int>> ele[N], com[N];

int trace(int u)
{
    return dsu[u] < 0 ? u : dsu[u] = trace(dsu[u]);
}

void connect(int u, int v, int ind)
{
    if ((u = trace(u)) == (v = trace(v)))
        return;
    if (dsu[u] > dsu[v])
        swap(u, v);
    dsu[u] += dsu[v];
    dsu[v] = u;
    for (pair<int, int> &tmp : ele[v])
    {
        int cur = tmp.fi;
        ele[u].push_back({cur, ind});
        com[cur].push_back({u, ind});
    }
}

void Init(int k, std::vector<int> f, std::vector<int> s, std::vector<int> e)
{
    int n = f.size();
    for (int i = 0; i < n; i++)
    {
        dsu[i] = -1;
        col[f[i]].push_back(i);
        ele[i].push_back({i, -1});
        com[i].push_back({i, -1});
    }
    m = s.size();
    for (int i = 0; i < m; i++)
    {
        int u = s[m - 1 - i], v = e[m - 1 - i];
        connect(u, v, i);
    }
    for (int i = 0; i < n; i++)
    {
        for (pair<int, int> &v : ele[i])
            v.fi = f[v.fi];
        sort(ele[i].begin(), ele[i].end());
    }
}

int Separate(int u, int v)
{
    if (col[u].size() > col[v].size() || (col[u].size() == col[v].size() && u > v))
        swap(u, v);
    if (ma.count({u, v}) > 0)
        return ma[{u, v}];
    int ans = m + 1;
    for (int &x : col[u])
    {
        int le = 0, ri = com[x].size();
        while (le <= ri)
        {
            int mi = (le + ri) / 2;
            int cur = com[x][mi].fi;
            auto it = lower_bound(ele[cur].begin(), ele[cur].end(), make_pair(v, -1));
            if (it == ele[cur].end() || it->fi != v)
                le = mi + 1;
            else
            {
                ans = min(ans, max(com[x][mi].se, it->se));
                ri = mi - 1;
            }
        }
    }
    return ma[{u, v}] = m - ans;
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 398 ms 32636 KB Output is correct
2 Correct 364 ms 32728 KB Output is correct
3 Correct 362 ms 32716 KB Output is correct
4 Correct 362 ms 32816 KB Output is correct
5 Correct 367 ms 32844 KB Output is correct
6 Correct 370 ms 32692 KB Output is correct
7 Correct 379 ms 32684 KB Output is correct
8 Correct 363 ms 32564 KB Output is correct
9 Correct 387 ms 32632 KB Output is correct
10 Correct 372 ms 32676 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Correct 8 ms 7288 KB Output is correct
3 Correct 248 ms 28676 KB Output is correct
4 Correct 379 ms 28616 KB Output is correct
5 Correct 551 ms 28388 KB Output is correct
6 Correct 907 ms 28696 KB Output is correct
7 Correct 1579 ms 28752 KB Output is correct
8 Correct 3380 ms 28652 KB Output is correct
9 Correct 2662 ms 29248 KB Output is correct
10 Correct 2045 ms 29360 KB Output is correct
11 Correct 1978 ms 29372 KB Output is correct
12 Correct 1962 ms 29268 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 7288 KB Output is correct
2 Correct 8 ms 7288 KB Output is correct
3 Correct 398 ms 32636 KB Output is correct
4 Correct 364 ms 32728 KB Output is correct
5 Correct 362 ms 32716 KB Output is correct
6 Correct 362 ms 32816 KB Output is correct
7 Correct 367 ms 32844 KB Output is correct
8 Correct 370 ms 32692 KB Output is correct
9 Correct 379 ms 32684 KB Output is correct
10 Correct 363 ms 32564 KB Output is correct
11 Correct 387 ms 32632 KB Output is correct
12 Correct 372 ms 32676 KB Output is correct
13 Correct 248 ms 28676 KB Output is correct
14 Correct 379 ms 28616 KB Output is correct
15 Correct 551 ms 28388 KB Output is correct
16 Correct 907 ms 28696 KB Output is correct
17 Correct 1579 ms 28752 KB Output is correct
18 Correct 3380 ms 28652 KB Output is correct
19 Correct 2662 ms 29248 KB Output is correct
20 Correct 2045 ms 29360 KB Output is correct
21 Correct 1978 ms 29372 KB Output is correct
22 Correct 1962 ms 29268 KB Output is correct
23 Correct 1653 ms 29520 KB Output is correct
24 Correct 886 ms 29852 KB Output is correct
25 Correct 708 ms 29816 KB Output is correct
26 Correct 578 ms 29876 KB Output is correct
27 Correct 491 ms 30012 KB Output is correct
28 Correct 410 ms 30800 KB Output is correct
29 Correct 404 ms 31036 KB Output is correct
30 Correct 383 ms 31976 KB Output is correct
31 Correct 396 ms 32444 KB Output is correct
32 Correct 368 ms 32648 KB Output is correct