Submission #1867437


Source Code Expand

#define _USE_MATH_DEFINES
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <utility>
#include <complex>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <deque>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <random>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef complex<ld> compd;
#define rep(i,n)	for(int i=0;i<n;i++)
#define srep(i,a,n)	for(int i=a;i<n;i++)
#define REP(i,n)	for(int i=0;i<=n;i++)
#define SREP(i,a,n)	for(int i=a;i<=n;i++)
#define rrep(i,n)	for(int i=n-1;i>=0;i--)
#define RREP(i,n)	for(int i=n;i>=0;i--)
#define all(a)	(a).begin(),(a).end()
#define mp(a,b)	make_pair(a,b)
#define mt	make_tuple
#define pb	push_back
#define fst	first
#define scn second
#define bicnt(x)	__buildin__popcount(x)
#define gcd(a,b)	__gcd__(a,b)
#define debug(x)	cout<<"debug: "<<x<<endl
#define DEBUG 0
const ll inf = (ll)1e9;
const ll mod = 1e9 + 7;
const ld eps = 1e-9;
const int dx[] = { 0,1,0,-1 };
const int dy[] = { 1,0,-1,0 };

int parent[100000];
vint use[100010];

int findparent(int i) {
	return (i == parent[i] ? i : parent[i] = findparent(parent[i]));
}

void merge(int i, int j) {
	i = findparent(i);
	j = findparent(j);
	parent[i] = j;
}

int main() {
	int n, m;	cin >> n >> m;
	vint a(m), b(m);
	rep(i, m) {
		cin >> a[i] >> b[i];
		a[i]--;	b[i]--;
	}
	int q;	cin >> q;
	vint x(q), y(q), l(q, 0), r(q, m + 1);
	rep(i, q) {
		cin >> x[i] >> y[i];
		x[i]--;	y[i]--;
	}
	rep(t, 50) {
		rep(i, n)	parent[i] = i;
		rep(i, q) use[(l[i] + r[i]) / 2].push_back(i);
		SREP(i,1,m) {
			merge(a[i-1], b[i-1]);
			rep(j, use[i].size()) {
				if (findparent(x[use[i][j]]) == findparent(y[use[i][j]]))	r[use[i][j]] = i;
				else	l[use[i][j]] = i;
			}
			use[i].clear();
		}
	}
	rep(i, q)	cout << (findparent(x[i])!=findparent(y[i]) ? -1 : r[i]) << endl;
	return 0;
}

Submission Info

Submission Time
Task H - Union Sets
User fiord
Language C++14 (GCC 5.4.1)
Score 600
Code Size 2148 Byte
Status AC
Exec Time 924 ms
Memory 38244 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 49
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All sample_01.txt, sample_02.txt, sample_03.txt, subtask_1_1.txt, subtask_1_10.txt, subtask_1_11.txt, subtask_1_12.txt, subtask_1_13.txt, subtask_1_14.txt, subtask_1_15.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_2.txt, subtask_1_20.txt, subtask_1_21.txt, subtask_1_22.txt, subtask_1_23.txt, subtask_1_24.txt, subtask_1_25.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_3.txt, subtask_1_30.txt, subtask_1_31.txt, subtask_1_32.txt, subtask_1_33.txt, subtask_1_34.txt, subtask_1_35.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_4.txt, subtask_1_40.txt, subtask_1_41.txt, subtask_1_42.txt, subtask_1_43.txt, subtask_1_44.txt, subtask_1_45.txt, subtask_1_46.txt, subtask_1_5.txt, subtask_1_6.txt, subtask_1_7.txt, subtask_1_8.txt, subtask_1_9.txt
Case Name Status Exec Time Memory
sample_01.txt AC 2 ms 2560 KB
sample_02.txt AC 2 ms 2560 KB
sample_03.txt AC 2 ms 2560 KB
subtask_1_1.txt AC 2 ms 2560 KB
subtask_1_10.txt AC 50 ms 3200 KB
subtask_1_11.txt AC 288 ms 9084 KB
subtask_1_12.txt AC 5 ms 2816 KB
subtask_1_13.txt AC 8 ms 2688 KB
subtask_1_14.txt AC 3 ms 2816 KB
subtask_1_15.txt AC 91 ms 4736 KB
subtask_1_16.txt AC 9 ms 2688 KB
subtask_1_17.txt AC 23 ms 3744 KB
subtask_1_18.txt AC 3 ms 2560 KB
subtask_1_19.txt AC 11 ms 2816 KB
subtask_1_2.txt AC 2 ms 2560 KB
subtask_1_20.txt AC 3 ms 2560 KB
subtask_1_21.txt AC 15 ms 2816 KB
subtask_1_22.txt AC 3 ms 2688 KB
subtask_1_23.txt AC 246 ms 6520 KB
subtask_1_24.txt AC 248 ms 7652 KB
subtask_1_25.txt AC 251 ms 8956 KB
subtask_1_26.txt AC 274 ms 10488 KB
subtask_1_27.txt AC 656 ms 13400 KB
subtask_1_28.txt AC 641 ms 13196 KB
subtask_1_29.txt AC 246 ms 6520 KB
subtask_1_3.txt AC 2 ms 2560 KB
subtask_1_30.txt AC 248 ms 7652 KB
subtask_1_31.txt AC 251 ms 8828 KB
subtask_1_32.txt AC 283 ms 10488 KB
subtask_1_33.txt AC 529 ms 12992 KB
subtask_1_34.txt AC 527 ms 15132 KB
subtask_1_35.txt AC 246 ms 6520 KB
subtask_1_36.txt AC 251 ms 7652 KB
subtask_1_37.txt AC 250 ms 8952 KB
subtask_1_38.txt AC 283 ms 10716 KB
subtask_1_39.txt AC 922 ms 16760 KB
subtask_1_4.txt AC 13 ms 2944 KB
subtask_1_40.txt AC 924 ms 16760 KB
subtask_1_41.txt AC 211 ms 37732 KB
subtask_1_42.txt AC 258 ms 6416 KB
subtask_1_43.txt AC 432 ms 12164 KB
subtask_1_44.txt AC 512 ms 12832 KB
subtask_1_45.txt AC 207 ms 37604 KB
subtask_1_46.txt AC 235 ms 38244 KB
subtask_1_5.txt AC 62 ms 3328 KB
subtask_1_6.txt AC 5 ms 2816 KB
subtask_1_7.txt AC 2 ms 2560 KB
subtask_1_8.txt AC 3 ms 2688 KB
subtask_1_9.txt AC 41 ms 3072 KB