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 |
|
|
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 |