Submission #8087988
Source Code Expand
#include <bits/stdc++.h>
// #include <iostream> // cout, endl, cin
// #include <string> // string, to_string, stoi
// #include <vector> // vector
// #include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
// #include <utility> // pair, make_pair
// #include <tuple> // tuple, make_tuple
// #include <cstdint> // int64_t, int*_t
// #include <cstdio> // printf
// #include <map> // map
// #include <queue> // queue, priority_queue
// #include <set> // set
// #include <stack> // stack
// #include <deque> // deque
// #include <unordered_map> // unordered_map
// #include <unordered_set> // unordered_set
// #include <bitset> // bitset
// #include <climits>
// #include <cmath>
// #include <iomanip>
// #include <functional>
// #include <numeric>
// #include <random>
using namespace std;
#define int long long
#define pb push_back
#define F first
#define S second
#define FOR(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) FOR(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define ve vector
#define vi vector<int>
#define vp vector<pair<int,int>>
#define vvi vector<vector<int>>
template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>;
using ll = long long;
ll INF = LLONG_MAX / 4000 - 100;
ll mod = 1e9 + 7;
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
vector<ll> prime;
class fact {
public:
int fmod = 1e9+7;
vector<int> fac, finv, inv;
fact (int n, int Mod = 1e9+7) {
fmod = Mod;
fac = vector<int>(n + 1, 0);
finv = vector<int>(n + 1, 0);
inv = vector<int>(n + 1, 0);
fac[0] = 1; for (int i = 1; i < n + 1; i++) fac[i] = fac[i-1] * i % fmod;
for (int i = 0;i < n + 1;i++) finv[i] = fact::POW(fac[i], fmod-2);
for (int i = 0;i < n + 1;i++) inv[i] = POW(i, fmod-2);
}
ll nCr(ll n, ll r) {if(n < r) return 0; return (fac[n] * finv[r] % fmod) * finv[n-r] % fmod;}
ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%fmod;}a = a * a%fmod; b >>= 1;}return c;}
inline int operator [] (int i) {return fac[i];}
};
template <class T = ll> T in() {T x; cin >> x; return (x);}
void DEBUG(vector<int> a) {for(int i=0;i<a.size();i++)cout<<a[i]<<" ";cout<<endl;}
void EMP(int x) {cout<<"!!!"<<x<<"!!!"<<endl;}
ll GCD(ll a, ll b) {ll c; while (b != 0) {c = a % b; a = b; b = c;}return a;}
ll LCM(ll a, ll b) {return (a / GCD(a, b)) * (b / GCD(a, b)) * GCD(a, b);}
ll POW(ll a, ll b) {ll c = 1; while (b > 0) {if (b & 1) {c = a * c%mod;}a = a * a%mod; b >>= 1;}return c;}
void PRI(ll n) {bool a[n + 1LL]; for (int i = 0; i < n + 1LL; i++) {a[i] = 1LL;}for (int i = 2; i < n + 1LL; i++) {if (a[i]) {prime.pb(i); ll b = i; while (b <= n) {a[b] = 0; b += i;}}}}
template <typename T> T chmin(T& a, T b) {if(a>b)a=b;return a;}
template <typename T> T chmax(T& a, T b) {if(a<b)a=b;return b;}
bool isSqrt(ll a) {return pow(sqrt(a),2) == a ? 1 : 0;}
void YesNo(bool a) {if (a) cout << "Yes"; else cout << "No"; cout << endl;}
void yesno(bool a) {if (a) cout << "yes"; else cout << "no"; cout << endl;}
void YESNO(bool a) {if (a) cout << "YES"; else cout << "NO"; cout << endl;}
double dis(int x1, int x2, int y1, int y2) {
return sqrt((double)abs(x1-x2)*(double)abs(x1-x2)+(double)abs(y1-y2)*(double)abs(y1-y2));
}
int ceili(int x, int y) {
if (x % y == 0) return x / y;
else return x / y + 1;
}
long long extGCD(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
}
long long d = extGCD(b, a % b, y, x);
y -= a / b * x;
return d;
}
class UnionFind {
private:
vector<int> par;
public:
UnionFind(int N) { par = vector<int>(N, -1); }
int find(int x);
ll size(int x);
void unite(int x, int y);
bool same(int x, int y);
};
int UnionFind::find(int x) {
if (par[x] < 0) return x;
else return par[x] = find(par[x]);
}
ll UnionFind::size(int x) {
return -par[find(x)];
}
void UnionFind::unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
//大きい方に小さい方をくっ付ける
if (size(x) < size(y)) swap(x, y);
par[x] += par[y];
par[y] = x;
}
bool UnionFind::same(int x, int y) {
x = find(x);
y = find(y);
return x == y;
}
void solve() {
int n, m; cin >> n >> m;
vi A(m), B(m);
rep (i, m) cin >> A[i] >> B[i];
int q; cin >> q;
vi X(q), Y(q);
rep (i, q) {
cin >> X[i] >> Y[i];
}
vi ok(q, m), ng(q, -1);
while (true) {
bool finish = true;
vvi mid(m);
rep (i, q) {
if (ok[i] - ng[i] > 1) {
finish = false;
int mi = (ok[i] + ng[i]) / 2;
mid[mi].pb(i);
}
}
if (finish) break;
UnionFind uf(n);
rep (i, m) {
uf.unite(A[i], B[i]);
for (auto idx : mid[i]) (uf.same(X[idx], Y[idx]) ? ok[idx] : ng[idx]) = i;
}
}
rep (i, q) {
cout << ok[i] + 1 << endl;
}
return;
}
signed main() {
cin.tie(0);
ios::sync_with_stdio(false);
solve();
}
Submission Info
Submission Time |
|
Task |
H - Union Sets |
User |
harady |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
5262 Byte |
Status |
RE |
Exec Time |
311 ms |
Memory |
267236 KB |
Judge Result
Set Name |
Sample |
All |
Score / Max Score |
0 / 0 |
0 / 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 |
RE |
95 ms |
256 KB |
sample_02.txt |
RE |
95 ms |
256 KB |
sample_03.txt |
WA |
1 ms |
256 KB |
subtask_1_1.txt |
WA |
1 ms |
256 KB |
subtask_1_10.txt |
RE |
104 ms |
2560 KB |
subtask_1_11.txt |
RE |
119 ms |
6268 KB |
subtask_1_12.txt |
WA |
3 ms |
640 KB |
subtask_1_13.txt |
RE |
96 ms |
512 KB |
subtask_1_14.txt |
RE |
95 ms |
256 KB |
subtask_1_15.txt |
RE |
248 ms |
263780 KB |
subtask_1_16.txt |
RE |
243 ms |
262644 KB |
subtask_1_17.txt |
RE |
97 ms |
640 KB |
subtask_1_18.txt |
RE |
95 ms |
256 KB |
subtask_1_19.txt |
WA |
6 ms |
940 KB |
subtask_1_2.txt |
AC |
1 ms |
256 KB |
subtask_1_20.txt |
RE |
95 ms |
256 KB |
subtask_1_21.txt |
RE |
95 ms |
512 KB |
subtask_1_22.txt |
WA |
2 ms |
512 KB |
subtask_1_23.txt |
WA |
180 ms |
5204 KB |
subtask_1_24.txt |
WA |
182 ms |
5272 KB |
subtask_1_25.txt |
WA |
185 ms |
5304 KB |
subtask_1_26.txt |
WA |
198 ms |
5656 KB |
subtask_1_27.txt |
WA |
296 ms |
9900 KB |
subtask_1_28.txt |
WA |
297 ms |
9984 KB |
subtask_1_29.txt |
WA |
175 ms |
5204 KB |
subtask_1_3.txt |
RE |
95 ms |
256 KB |
subtask_1_30.txt |
WA |
182 ms |
5272 KB |
subtask_1_31.txt |
WA |
182 ms |
5304 KB |
subtask_1_32.txt |
WA |
197 ms |
5656 KB |
subtask_1_33.txt |
WA |
287 ms |
9900 KB |
subtask_1_34.txt |
WA |
287 ms |
9644 KB |
subtask_1_35.txt |
WA |
178 ms |
5204 KB |
subtask_1_36.txt |
WA |
179 ms |
5272 KB |
subtask_1_37.txt |
WA |
188 ms |
5304 KB |
subtask_1_38.txt |
WA |
197 ms |
5648 KB |
subtask_1_39.txt |
WA |
309 ms |
9760 KB |
subtask_1_4.txt |
WA |
6 ms |
1152 KB |
subtask_1_40.txt |
WA |
311 ms |
9816 KB |
subtask_1_41.txt |
RE |
107 ms |
4600 KB |
subtask_1_42.txt |
RE |
257 ms |
267236 KB |
subtask_1_43.txt |
WA |
252 ms |
7840 KB |
subtask_1_44.txt |
WA |
273 ms |
9900 KB |
subtask_1_45.txt |
WA |
166 ms |
3584 KB |
subtask_1_46.txt |
WA |
167 ms |
3584 KB |
subtask_1_5.txt |
RE |
101 ms |
2560 KB |
subtask_1_6.txt |
WA |
3 ms |
768 KB |
subtask_1_7.txt |
WA |
1 ms |
256 KB |
subtask_1_8.txt |
WA |
1 ms |
384 KB |
subtask_1_9.txt |
WA |
30 ms |
1152 KB |