Submission #150808

#	Time	Username	Problem	Language	Result	Execution time	Memory
150808		graneli (#200)	Trip to the Galapagos Islands (FXCUP4_island)	C++17	0 / 100	392 ms	45792 KiB

island

#include "island.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define mp make_pair
#define pb push_back
//#define ll __int128
#define ll long long
#define LEFT(a) ((a)<<1)
#define RIGHT(a) (LEFT(a) + 1)
#define MID(a,b) ((a+b)>>1)
#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define y1 y122
using namespace std;

const int N = 300005;

int n, m;
vector < int > V[N];
int par[N];
set < pair < int, int > > S[N];

void Init(int K, std::vector<int> F, std::vector<int> Ss, std::vector<int> E){
	n = F.size(), m = Ss.size();
	// ToDo
	for (int i = 0; i < n; i++){
        S[i].insert ({m, i});
        par[i] = i;
        V[i].pb (i);
	}
	for (int i = m - 1; i >= 0; i--){
        int u = Ss[i], v = E[i];
        u = par[u];
        v = par[v];
        if (u == v)
            continue;
        if ((int)V[u].size() > (int)V[v].size())
            swap (u, v);
        for (int x : V[u]){
            par[x] = v;
            V[v].pb (x);
            S[x].insert ({i, v});
        }
        V[u].clear();
	}
}

int Separate(int A, int B){
    int l = 0, r = m - 1;
    //cout << A << " " << B << endl;
    while (l < r){
        int mid = l + r + 1 >> 1;
        int x, y;
        auto I = S[A].lower_bound ({mid, 0});
        x = (*I).S;
        I = S[B].lower_bound ({mid, 0});
        y = (*I).S;
        //cout << mid << " " << x << " " << y << endl;
        if (x == y)
            l = mid;
        else
            r = mid - 1;
    }
	return l;
}

Compilation message (stderr)

island.cpp: In function 'int Separate(int, int)':
island.cpp:53:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = l + r + 1 >> 1;
                   ~~~~~~^~~

• Subtask 1: 0 / 31
• Subtask 2: 0 / 39
• Subtask 3: 0 / 30