QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#267587 | #7869. 建设终末树 | hos_lyric# | 55 | 511ms | 201928kb | C++14 | 12.4kb | 2023-11-27 14:51:28 | 2024-07-04 03:09:44 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
struct Scc {
int n;
vector<int> as, bs;
vector<int> ptr, zu, us;
int l;
vector<int> ids;
int operator[](int u) const { return ids[u]; }
explicit Scc(int n_) : n(n_), as(), bs(), l(-1) {}
void ae(int u, int v) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
as.push_back(u);
bs.push_back(v);
}
void dfs0(int u) {
if (!ids[u]) {
ids[u] = -1;
for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs0(zu[i]);
us.push_back(u);
}
}
void dfs1(int u) {
if (!~ids[u]) {
ids[u] = l;
for (int i = ptr[u]; i < ptr[u + 1]; ++i) dfs1(zu[i]);
}
}
void run() {
const int m = as.size();
ptr.resize(n + 2);
zu.resize(m);
for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
for (int i = 0; i < m; ++i) ++ptr[as[i] + 2];
for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
for (int i = 0; i < m; ++i) zu[ptr[as[i] + 1]++] = bs[i];
ids.assign(n, 0);
us.clear();
for (int u = 0; u < n; ++u) dfs0(u);
for (int u = 0; u < n + 2; ++u) ptr[u] = 0;
for (int i = 0; i < m; ++i) ++ptr[bs[i] + 2];
for (int u = 2; u < n + 1; ++u) ptr[u + 1] += ptr[u];
for (int i = 0; i < m; ++i) zu[ptr[bs[i] + 1]++] = as[i];
l = 0;
for (int j = n; --j >= 0; ) if (!~ids[us[j]]) { dfs1(us[j]); ++l; }
}
vector<vector<int>> group() const {
assert(~l);
vector<vector<int>> uss(l);
for (int u = 0; u < n; ++u) uss[ids[u]].push_back(u);
return uss;
}
};
struct Hld {
int n, rt;
// needs to be tree
// vertex lists
// modified in build(rt) (parent removed, heavy child first)
vector<vector<int>> graph;
vector<int> sz, par, dep;
int zeit;
vector<int> dis, fin, sid;
// head vertex (minimum depth) in heavy path
vector<int> head;
Hld() : n(0), rt(-1), zeit(0) {}
explicit Hld(int n_) : n(n_), rt(-1), graph(n), zeit(0) {}
void ae(int u, int v) {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfsSz(int u) {
sz[u] = 1;
for (const int v : graph[u]) {
auto it = std::find(graph[v].begin(), graph[v].end(), u);
if (it != graph[v].end()) graph[v].erase(it);
par[v] = u;
dep[v] = dep[u] + 1;
dfsSz(v);
sz[u] += sz[v];
}
}
void dfsHld(int u) {
dis[u] = zeit++;
const int deg = graph[u].size();
if (deg > 0) {
int vm = graph[u][0];
int jm = 0;
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
if (sz[vm] < sz[v]) {
vm = v;
jm = j;
}
}
swap(graph[u][0], graph[u][jm]);
head[vm] = head[u];
dfsHld(vm);
for (int j = 1; j < deg; ++j) {
const int v = graph[u][j];
head[v] = v;
dfsHld(v);
}
}
fin[u] = zeit;
}
void build(int rt_) {
assert(0 <= rt_); assert(rt_ < n);
rt = rt_;
sz.assign(n, 0);
par.assign(n, -1);
dep.assign(n, -1);
dep[rt] = 0;
dfsSz(rt);
zeit = 0;
dis.assign(n, -1);
fin.assign(n, -1);
head.assign(n, -1);
head[rt] = rt;
dfsHld(rt);
assert(zeit == n);
sid.assign(n, -1);
for (int u = 0; u < n; ++u) sid[dis[u]] = u;
}
friend ostream &operator<<(ostream &os, const Hld &hld) {
const int maxDep = *max_element(hld.dep.begin(), hld.dep.end());
vector<string> ss(2 * maxDep + 1);
int pos = 0, maxPos = 0;
for (int j = 0; j < hld.n; ++j) {
const int u = hld.sid[j];
const int d = hld.dep[u];
if (hld.head[u] == u) {
if (j != 0) {
pos = maxPos + 1;
ss[2 * d - 1].resize(pos, '-');
ss[2 * d - 1] += '+';
}
} else {
ss[2 * d - 1].resize(pos, ' ');
ss[2 * d - 1] += '|';
}
ss[2 * d].resize(pos, ' ');
ss[2 * d] += std::to_string(u);
if (maxPos < static_cast<int>(ss[2 * d].size())) {
maxPos = ss[2 * d].size();
}
}
for (int d = 0; d <= 2 * maxDep; ++d) os << ss[d] << '\n';
return os;
}
bool contains(int u, int v) const {
return (dis[u] <= dis[v] && dis[v] < fin[u]);
}
int lca(int u, int v) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
for (; head[u] != head[v]; ) (dis[u] > dis[v]) ? (u = par[head[u]]) : (v = par[head[v]]);
return (dis[u] > dis[v]) ? v : u;
}
int jumpUp(int u, int d) const {
assert(0 <= u); assert(u < n);
assert(d >= 0);
if (dep[u] < d) return -1;
const int tar = dep[u] - d;
for (u = head[u]; ; u = head[par[u]]) {
if (dep[u] <= tar) return sid[dis[u] + (tar - dep[u])];
}
}
int jump(int u, int v, int d) const {
assert(0 <= u); assert(u < n);
assert(0 <= v); assert(v < n);
assert(d >= 0);
const int l = lca(u, v);
const int du = dep[u] - dep[l], dv = dep[v] - dep[l];
if (d <= du) {
return jumpUp(u, d);
} else if (d <= du + dv) {
return jumpUp(v, du + dv - d);
} else {
return -1;
}
}
// [u, v) or [u, v]
template <class F> void doPathUp(int u, int v, bool inclusive, F f) const {
assert(contains(v, u));
for (; head[u] != head[v]; u = par[head[u]]) f(dis[head[u]], dis[u] + 1);
if (inclusive) {
f(dis[v], dis[u] + 1);
} else {
if (v != u) f(dis[v] + 1, dis[u] + 1);
}
}
// not path order, include lca(u, v) or not
template <class F> void doPath(int u, int v, bool inclusive, F f) const {
const int l = lca(u, v);
doPathUp(u, l, false, f);
doPathUp(v, l, inclusive, f);
}
// (vs, ps): compressed tree
// vs: DFS order (sorted by dis)
// vs[ps[x]]: the parent of vs[x]
// ids[vs[x]] = x, not set for non-tree vertex
vector<int> ids;
pair<vector<int>, vector<int>> compress(vector<int> us) {
// O(n) first time
ids.resize(n, -1);
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
int usLen = us.size();
assert(usLen >= 1);
for (int x = 1; x < usLen; ++x) us.push_back(lca(us[x - 1], us[x]));
std::sort(us.begin(), us.end(), [&](int u, int v) -> bool {
return (dis[u] < dis[v]);
});
us.erase(std::unique(us.begin(), us.end()), us.end());
usLen = us.size();
for (int x = 0; x < usLen; ++x) ids[us[x]] = x;
vector<int> ps(usLen, -1);
for (int x = 1; x < usLen; ++x) ps[x] = ids[lca(us[x - 1], us[x])];
return make_pair(us, ps);
}
};
////////////////////////////////////////////////////////////////////////////////
int N, M, Q;
vector<int> A, B;
vector<vector<int>> C;
vector<vector<int>> V, S;
int main() {
for (; ~scanf("%d%d%d", &N, &M, &Q); ) {
A.resize(N - 1);
B.resize(N - 1);
for (int i = 0; i < N - 1; ++i) {
scanf("%d%d", &A[i], &B[i]);
--A[i];
--B[i];
}
C.resize(M);
for (int m = 0; m < M; ++m) {
int len;
scanf("%d", &len);
C[m].resize(len);
for (int &c : C[m]) {
scanf("%d", &c);
--c;
}
}
V.resize(Q);
S.resize(Q);
for (int q = 0; q < Q; ++q) {
int len;
scanf("%d", &len);
V[q].resize(len);
for (int &v : V[q]) {
scanf("%d", &v);
--v;
}
scanf("%d", &len);
S[q].resize(len);
for (int &s : S[q]) {
scanf("%d", &s);
--s;
}
}
Hld hld(N);
for (int i = 0; i < N - 1; ++i) {
hld.ae(A[i], B[i]);
}
hld.build(0);
const auto &par = hld.par;
const auto &sid = hld.sid;
#ifdef LOCAL
cerr<<string(80,'=')<<endl;
cerr<<hld<<endl;
cerr<<"C = "<<C<<endl;
cerr<<"V = "<<V<<endl;
cerr<<"S = "<<S<<endl;
#endif
// m < M: item m is in subtree(u)
// m >= M: all items in S[q] must be in subtree(u)
auto tru = [&](int m, int u) -> int { return (m * N + u) << 1; };
auto fal = [&](int m, int u) -> int { return (m * N + u) << 1 | 1; };
auto prefix = [&](int m, int u) -> int { return ((M + Q) * N + (m * N + u)) << 1; };
Scc scc(((M + Q) * N + M * N) << 1);
// x ==> y
auto add = [&](int x, int y) -> void {
if (x != y) {
scc.ae(x, y);
if ((x ^ 1) != y) {
scc.ae(y ^ 1, x ^ 1);
}
}
};
for (int m = 0; m < M; ++m) {
vector<int> dp(N, 0);
for (const int c : C[m]) {
dp[c] += 1;
}
for (int j = N; --j >= 1; ) {
const int u = sid[j];
dp[par[u]] += dp[u];
}
for (int u = 0; u < N; ++u) {
if (dp[u] == (int)C[m].size()) add(fal(m, u), tru(m, u));
if (dp[u] == 0) add(tru(m, u), fal(m, u));
}
for (int u = 1; u < N; ++u) {
add(tru(m, u), tru(m, par[u]));
}
for (int u = 0; u < N; ++u) {
const auto &vs = hld.graph[u];
/*
for (int j0 = 0; j0 < (int)vs.size(); ++j0) for (int j1 = j0 + 1; j1 < (int)vs.size(); ++j1) {
add(tru(m, vs[j0]), fal(m, vs[j1]));
}
*/
const int len = vs.size();
for (int j = 1; j < len; ++j) {
add(prefix(m, vs[j - 1]), prefix(m, vs[j]));
}
for (int j = 0; j < len; ++j) {
add(tru(m, vs[j]), prefix(m, vs[j]));
if (j) add(tru(m, vs[j]), prefix(m, vs[j - 1]) ^ 1);
}
}
}
for (int q = 0; q < Q; ++q) {
/*
vector<int> dp(N, 0);
for (const int v : V[q]) {
dp[v] += 1;
}
for (int j = N; --j >= 1; ) {
const int u = sid[j];
dp[par[u]] += dp[u];
}
for (int u = 0; u < N; ++u) {
if (dp[u] == (int)V[q].size()) continue;
if (dp[u] == 0) continue;
// same side when cut (par[u], u)
for (const int m0 : S[q]) for (const int m1 : S[q]) {
add(tru(m0, u), tru(m1, u));
}
}
*/
const auto vsps = hld.compress(V[q]);
const int len = vsps.first.size();
// cerr<<V[q]<<": "<<vsps<<endl;
for (int j = 1; j < len; ++j) {
const int p = vsps.first[vsps.second[j]];
for (int u = vsps.first[j]; u != p; u = par[u]) {
// same side when cut (par[u], u)
for (const int m : S[q]) {
add(tru(m, u), tru(M + q, u));
}
for (const int m : S[q]) {
add(tru(M + q, u), tru(m, u));
}
}
}
}
scc.run();
bool ok = true;
for (int x = 0; x < scc.n; x += 2) {
ok = ok && (scc[x] != scc[x ^ 1]);
}
if (ok) {
vector<int> ans(M, -1);
for (int m = 0; m < M; ++m) {
// for(int u=0;u<N;++u)cerr<<(scc[fal(m,u)]<scc[tru(m,u)]);cerr<<endl;
for (int j = N; --j >= 0; ) {
const int u = sid[j];
if (scc[fal(m, u)] < scc[tru(m, u)]) {
ans[m] = u;
break;
}
}
}
for (int m = 0; m < M; ++m) {
if (m) printf(" ");
printf("%d", ans[m] + 1);
}
puts("");
} else {
puts("-1");
}
}
return 0;
}
詳細信息
Subtask #1:
score: 0
Time Limit Exceeded
Test #1:
score: 0
Time Limit Exceeded
input:
1999 1998 27199 1368 233 233 617 233 388 233 1127 1905 233 907 233 233 40 233 1325 233 1940 1739 233 501 233 233 33 735 233 233 283 233 1427 1992 233 233 632 233 685 1188 233 648 233 233 344 233 1321 986 233 848 233 770 233 256 233 164 233 936 233 1206 233 53 233 1054 233 1430 233 1714 233 86 233 11...
output:
result:
Subtask #2:
score: 15
Accepted
Test #8:
score: 15
Accepted
time: 1ms
memory: 3916kb
input:
10 10 8 4 2 2 9 6 9 8 7 4 10 7 2 5 2 2 1 5 3 3 10 7 2 2 10 2 2 4 10 2 10 4 2 8 2 2 4 10 1 8 2 2 10 1 1 1 10 2 10 9 3 10 3 4 2 7 1 3 10 6 3 2 4 8 2 3 2 4 2 9 4 6 2 5 7 2 3 9 2 2 1 4 10 6 8 5 4 10 6 1 2 2 1 4 2 7 5 2 5 3 2 8 3
output:
10 10 10 10 2 10 8 2 1 10
result:
ok Accepted.
Test #9:
score: 0
Accepted
time: 0ms
memory: 3896kb
input:
10 10 9 9 10 3 5 2 3 9 2 2 6 1 3 8 5 1 7 6 4 1 7 1 8 2 10 2 4 8 5 1 2 2 10 9 2 2 7 1 8 4 1 8 5 2 2 10 6 4 9 2 4 3 2 3 10 2 5 3 2 8 3 2 8 5 2 5 3 2 6 5 2 5 9 2 9 3 2 9 8 2 1 8 3 7 1 6 2 2 8 2 10 2 3 8 1 4 2 9 5 3 1 6 8 3 9 4 3 2 1 7
output:
7 8 9 2 9 3 8 3 9 3
result:
ok Accepted.
Test #10:
score: 0
Accepted
time: 0ms
memory: 4096kb
input:
10 10 8 7 1 3 2 6 1 2 1 3 5 10 8 4 7 9 2 6 10 1 9 2 3 5 2 10 8 3 9 1 5 1 9 2 1 8 1 10 4 2 7 9 3 3 9 3 6 3 1 9 3 3 3 1 2 3 8 2 9 2 1 9 2 8 9 2 4 2 3 2 8 9 3 4 9 6 3 7 3 6 2 7 10 2 5 8 2 5 9 2 1 5 3 9 7 1 2 9 4 3 8 3 7 3 7 6 3
output:
9 3 10 2 9 10 10 3 3 1
result:
ok Accepted.
Test #11:
score: 0
Accepted
time: 0ms
memory: 3660kb
input:
10 10 6 8 1 3 10 6 1 9 2 8 5 3 7 9 7 6 4 6 3 2 1 6 3 6 10 3 1 8 4 10 1 4 3 3 3 1 6 3 1 4 10 2 9 2 2 9 2 3 6 1 4 2 7 10 3 3 2 9 3 3 4 6 5 4 8 10 5 9 5 5 6 4 9 1 2 5 9 4 2 6 5 10 3 7 3 8 3 1 9 2 3 2 8 9 2 10 2 4 10 5 3 2 3 6 2 10
output:
-1
result:
ok Accepted.
Test #12:
score: 0
Accepted
time: 0ms
memory: 4136kb
input:
10 10 9 1 7 7 5 7 8 3 7 7 10 4 7 7 9 6 7 2 7 3 6 3 9 3 8 2 4 6 2 7 5 3 6 8 3 4 5 10 4 6 4 10 9 7 5 10 4 6 9 8 1 6 8 9 4 10 5 2 3 4 5 1 7 7 8 5 1 10 9 6 2 8 7 2 3 7 2 6 2 2 3 6 3 3 9 2 2 10 1 2 8 1 2 8 5 2 9 5 2 7 3 2 5 3 3 2 10 8 2 5 8 2 1 3 2 8 4 3 4 5 6 2 9 2 2 10 9 3 3 8 9
output:
7 7 7 7 7 7 7 7 7 7
result:
ok Accepted.
Test #13:
score: 0
Accepted
time: 0ms
memory: 4120kb
input:
10 10 6 4 9 8 4 4 7 3 4 5 4 2 4 4 6 1 4 10 4 9 8 1 6 4 9 10 5 3 2 5 4 2 10 7 3 2 4 6 2 6 4 8 2 6 10 5 3 9 1 8 8 7 9 10 6 5 3 2 1 8 7 8 10 5 2 1 9 3 8 5 10 7 6 2 9 8 3 9 10 5 7 1 8 9 3 2 6 6 3 2 6 10 5 7 3 5 2 4 2 10 4 4 10 6 8 2 3 10 5 2 4 3 1 8 5 2 6 9 3 7 4 10 6 8 9 7 3 6 1 4 3 8 7 2 3 5 10 2 2 5 ...
output:
1 4 4 4 4 4 4 4 4 4
result:
ok Accepted.
Test #14:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
10 10 7 10 6 10 4 2 10 8 10 10 1 5 10 3 10 7 10 9 10 5 8 1 3 5 6 10 2 10 8 5 7 9 3 6 4 1 7 4 8 6 10 3 5 9 2 1 10 7 7 6 10 8 4 1 9 1 5 9 9 4 6 10 1 7 2 3 5 10 6 4 3 9 1 5 8 7 2 10 2 8 2 8 6 1 3 5 7 4 8 9 3 8 5 4 3 10 5 4 2 10 4 3 4 2 10 3 6 7 1 3 4 10 5 2 6 3 2 7 2 4 8 7 6 4 3 8 3 9 4 10 8 4 5 3 10 2...
output:
1 1 10 10 10 5 10 10 10 10
result:
ok Accepted.
Test #15:
score: 0
Accepted
time: 0ms
memory: 3808kb
input:
10 10 9 8 7 5 3 1 8 7 6 10 4 3 6 1 2 5 9 9 4 5 7 6 9 1 10 3 10 5 9 2 9 6 2 3 4 5 10 6 5 4 3 3 9 3 8 4 3 8 2 10 3 8 4 2 5 3 9 10 8 2 1 5 2 5 7 2 7 4 2 10 7 2 7 9 2 6 5 2 8 1 2 8 1 2 3 5 2 3 10 4 5 8 3 7 3 2 4 5 2 7 5 3 5 1 2 2 1 6 2 2 10 2 8 4 2 2 8 2 7 1
output:
3 5 6 3 3 3 3 3 3 5
result:
ok Accepted.
Test #16:
score: 0
Accepted
time: 1ms
memory: 3720kb
input:
10 10 9 2 7 1 8 2 5 9 4 5 3 10 7 4 6 10 8 6 1 2 7 5 4 1 4 10 9 2 1 2 5 10 9 4 2 7 3 1 9 4 2 8 9 4 6 8 3 2 2 8 1 3 2 1 9 4 5 8 9 4 2 9 10 2 1 7 2 10 8 2 7 8 2 3 10 2 7 6 2 8 6 2 5 10 2 6 2 2 5 10 3 5 9 8 2 4 10 2 1 5 2 2 9 2 5 7 3 3 10 1 3 8 4 5 3 5 10 9
output:
-1
result:
ok Accepted.
Test #17:
score: 0
Accepted
time: 1ms
memory: 4132kb
input:
10 10 6 8 10 3 5 4 1 9 6 7 10 7 9 2 8 3 1 4 6 1 1 2 10 9 3 3 6 2 2 8 10 2 10 7 2 8 7 5 9 4 3 10 5 3 8 9 10 1 7 2 2 10 3 4 1 5 3 10 9 5 3 1 9 10 3 6 4 10 5 9 6 1 2 8 4 4 2 5 3 2 4 7 3 9 2 4 3 7 1 3 4 5 8 2 4 4 3 10 1 9 3 10 8 3
output:
1 10 10 10 10 10 1 10 7 10
result:
ok Accepted.
Test #18:
score: 0
Accepted
time: 0ms
memory: 3836kb
input:
10 10 8 3 4 2 8 1 4 1 9 7 5 7 6 5 8 6 10 10 9 2 10 2 3 10 1 2 4 8 5 7 1 2 10 2 1 10 4 1 9 8 5 6 4 8 6 5 2 9 2 1 9 4 7 1 9 2 6 10 2 4 3 9 8 2 9 4 3 1 4 2 2 7 4 3 6 8 7 2 7 8 2 10 7 3 7 3 1 3 2 9 1 3 10 1 3 2 4 1 3 8 5 6 2 4 9 2 8 1 2 9 2 3 3 6 2 3 6 7 8
output:
10 10 1 10 10 1 1 1 10 7
result:
ok Accepted.
Subtask #3:
score: 20
Accepted
Test #19:
score: 20
Accepted
time: 420ms
memory: 194912kb
input:
500 498 5000 60 409 462 125 461 410 42 178 133 372 137 265 358 27 450 294 45 454 76 405 132 118 333 331 365 230 114 218 112 377 49 429 60 299 488 95 85 362 89 33 426 308 427 198 468 481 289 363 195 430 61 21 162 55 12 487 395 85 79 475 391 215 244 351 331 43 452 186 247 271 224 390 206 347 447 165 9...
output:
498 368 6 72 163 77 212 74 6 269 322 74 74 359 243 48 373 402 253 1 500 71 184 361 455 36 104 235 25 390 305 390 469 369 74 309 415 133 239 429 231 425 74 389 47 429 235 74 200 235 341 253 275 174 1 378 452 74 29 485 266 213 4 47 1 21 479 342 390 375 207 365 235 472 378 253 435 92 402 350 431 322 10...
result:
ok Accepted.
Test #20:
score: 0
Accepted
time: 451ms
memory: 196144kb
input:
500 500 5000 297 429 444 310 304 235 470 8 33 395 174 34 276 320 298 478 149 117 400 211 118 399 448 268 446 484 268 180 465 471 68 443 33 358 256 431 490 452 110 389 304 418 286 219 498 16 416 376 495 173 408 138 473 228 317 199 344 279 31 469 159 16 377 397 492 402 308 107 461 11 332 105 377 77 31...
output:
39 252 124 376 313 200 48 31 336 117 179 31 481 203 415 380 65 292 114 244 60 6 15 60 357 441 370 279 296 38 41 65 44 133 422 463 65 179 423 79 446 489 405 83 357 376 472 65 223 371 354 265 481 280 377 74 87 70 171 481 436 471 203 163 237 409 65 13 114 280 249 321 65 481 13 416 348 110 357 387 306 3...
result:
ok Accepted.
Test #21:
score: 0
Accepted
time: 466ms
memory: 195732kb
input:
499 498 5000 28 246 54 26 13 312 346 225 377 80 274 410 352 446 394 386 204 453 54 355 337 480 313 263 90 395 388 61 193 71 213 265 125 121 65 120 154 216 331 206 475 413 263 332 322 306 75 290 335 222 149 360 89 139 52 10 91 132 202 88 211 106 205 422 19 467 250 156 382 223 161 486 4 8 495 16 64 12...
output:
147 176 407 490 57 147 62 438 354 405 442 225 434 33 117 57 269 136 57 211 369 176 442 438 441 47 24 221 98 405 277 198 375 172 136 6 475 57 314 62 377 166 57 107 305 200 344 57 229 136 71 200 10 369 78 301 6 57 221 200 438 172 48 358 458 21 7 395 254 455 133 405 274 200 298 412 117 200 200 355 342 ...
result:
ok Accepted.
Test #22:
score: 0
Accepted
time: 511ms
memory: 195376kb
input:
499 500 5000 71 225 374 470 413 420 422 368 357 141 479 360 172 237 21 40 16 386 434 274 188 207 249 16 9 259 152 63 488 264 166 467 51 70 90 417 209 411 43 101 102 206 320 29 110 408 182 333 115 394 138 458 29 296 73 241 392 145 235 428 197 114 271 125 131 401 122 377 215 252 186 253 38 309 11 491 ...
output:
66 299 375 188 163 22 391 82 378 357 4 497 260 82 188 378 82 82 260 378 220 4 220 363 378 4 390 363 260 163 323 82 391 497 357 463 295 363 82 66 21 497 91 82 497 390 91 497 220 497 375 91 378 22 390 295 118 93 260 284 497 82 22 91 463 375 463 497 22 21 391 93 21 299 263 21 4 22 463 82 391 497 22 263...
result:
ok Accepted.
Test #23:
score: 0
Accepted
time: 447ms
memory: 195444kb
input:
498 498 5000 181 300 371 226 361 224 82 101 233 476 366 273 212 240 90 169 488 477 22 374 164 369 276 390 350 61 101 165 331 274 72 325 371 190 472 404 250 449 179 451 64 153 447 267 97 24 495 168 139 170 203 407 493 225 413 216 29 490 306 332 257 309 43 279 189 94 294 287 297 319 289 406 221 338 74...
output:
178 489 439 71 71 326 44 448 270 71 274 8 63 145 8 71 96 326 274 178 109 437 491 391 437 326 96 140 63 343 270 437 439 489 274 224 178 491 324 481 448 270 391 8 251 489 437 274 491 97 473 124 8 97 343 491 8 44 473 124 491 63 391 178 489 97 448 343 489 324 448 481 481 439 489 489 489 178 437 391 71 2...
result:
ok Accepted.
Test #24:
score: 0
Accepted
time: 433ms
memory: 196456kb
input:
498 499 5000 49 110 380 351 80 59 60 4 378 224 383 28 95 381 220 227 287 440 251 493 278 388 157 339 489 377 98 308 122 403 267 47 109 207 140 31 461 264 210 481 130 216 31 410 383 9 141 13 343 448 45 324 297 449 371 149 474 214 41 154 185 138 299 34 412 411 492 327 277 229 33 494 237 12 97 420 6 18...
output:
187 412 483 390 412 483 93 483 412 483 483 390 412 483 483 412 483 93 412 93 187 412 187 483 431 93 187 483 390 187 93 483 390 390 390 93 187 390 483 187 93 187 93 390 187 187 187 187 412 483 187 483 187 483 187 483 483 390 187 93 483 412 412 187 483 412 483 187 412 390 483 390 483 187 412 390 93 41...
result:
ok Accepted.
Test #25:
score: 0
Accepted
time: 450ms
memory: 196252kb
input:
500 499 5000 368 181 285 335 445 454 267 331 22 212 294 281 454 121 19 31 57 14 101 152 130 284 329 396 406 500 446 115 337 61 421 68 203 119 352 238 313 450 16 259 167 307 326 255 173 256 77 42 203 270 249 402 153 135 146 450 172 73 185 149 398 15 426 213 407 368 351 124 159 356 371 418 319 156 304...
output:
355 210 461 310 461 210 210 310 355 461 461 19 461 487 487 461 19 355 310 461 310 487 355 487 487 487 310 487 355 487 210 487 210 210 355 355 487 461 487 355 19 355 355 487 210 487 487 310 355 461 210 355 487 310 487 487 487 487 19 355 19 461 461 487 461 19 224 210 210 210 461 355 19 461 210 461 210...
result:
ok Accepted.
Test #26:
score: 0
Accepted
time: 429ms
memory: 200812kb
input:
500 499 5000 350 140 294 337 407 172 180 28 139 287 2 413 498 218 4 449 245 412 45 247 397 482 427 165 202 490 53 323 178 209 247 341 253 485 478 203 34 305 306 173 111 14 188 64 213 9 278 59 347 454 83 448 356 336 148 239 378 272 145 402 457 189 299 209 291 368 96 110 187 270 218 304 358 217 6 455 ...
output:
-1
result:
ok Accepted.
Test #27:
score: 0
Accepted
time: 457ms
memory: 201768kb
input:
499 499 5000 75 164 439 163 466 334 370 484 25 201 107 165 250 122 355 17 411 164 169 9 463 497 428 442 93 50 7 326 15 207 479 112 454 391 329 96 127 290 1 2 99 347 39 84 407 405 147 271 57 298 472 129 195 377 296 35 441 440 232 176 388 92 325 198 425 267 23 100 487 433 78 416 193 365 348 352 324 28...
output:
-1
result:
ok Accepted.
Subtask #4:
score: 20
Accepted
Dependency #2:
100%
Accepted
Test #28:
score: 20
Accepted
time: 123ms
memory: 73772kb
input:
499 499 265 20 482 382 88 211 434 122 198 238 180 411 104 462 291 28 215 220 69 192 172 493 52 25 455 162 29 405 278 161 339 316 212 443 257 419 262 411 458 331 93 106 144 422 264 488 248 86 165 62 411 426 236 443 30 140 260 499 37 295 372 315 237 15 67 403 366 467 235 42 262 61 300 312 362 469 202 ...
output:
298 488 28 270 17 17 222 222 81 325 488 488 28 479 215 17 81 28 74 488 74 222 488 17 369 222 250 369 479 250 479 479 250 442 57 488 81 298 17 298 496 17 496 298 422 496 442 222 488 57 81 479 74 488 28 267 81 17 28 17 298 51 479 298 28 28 28 17 28 222 74 51 442 222 488 28 479 488 488 222 28 298 42 28...
result:
ok Accepted.
Test #29:
score: 0
Accepted
time: 121ms
memory: 73164kb
input:
500 498 275 323 261 41 144 117 22 223 61 412 79 403 191 166 56 401 274 42 204 439 277 439 175 475 382 320 164 179 397 143 302 68 276 11 9 252 25 421 419 109 353 451 165 63 461 28 241 7 91 302 420 60 284 283 113 418 176 443 177 64 412 144 497 493 14 483 209 287 375 287 100 298 376 298 193 188 321 288...
output:
156 491 491 11 339 168 11 420 144 157 420 208 193 76 157 157 160 208 76 339 208 76 11 229 193 157 491 191 193 56 191 156 491 420 157 157 420 11 156 144 420 156 76 160 160 156 76 193 420 420 302 156 11 420 156 193 193 156 11 420 41 420 11 156 11 237 156 160 11 156 156 156 11 420 11 11 157 420 491 237...
result:
ok Accepted.
Test #30:
score: 0
Accepted
time: 136ms
memory: 79648kb
input:
500 499 215 233 327 276 433 188 7 393 452 431 389 55 485 238 103 411 344 273 193 351 211 248 161 489 149 13 427 336 210 487 199 76 324 452 477 290 134 108 418 378 300 371 218 499 85 418 450 480 353 248 451 89 3 249 248 283 203 294 443 102 360 412 20 234 177 479 171 357 165 490 340 133 110 52 106 374...
output:
-1
result:
ok Accepted.
Test #31:
score: 0
Accepted
time: 124ms
memory: 76444kb
input:
499 499 260 157 101 80 132 333 13 206 419 136 233 322 168 48 362 32 485 426 214 493 349 179 181 245 284 332 366 234 63 407 254 429 337 32 217 469 130 18 129 147 42 223 473 9 310 330 6 242 483 233 228 154 498 31 351 171 377 455 328 497 301 343 244 355 144 386 489 437 247 307 493 134 316 185 256 199 2...
output:
-1
result:
ok Accepted.
Test #32:
score: 0
Accepted
time: 128ms
memory: 89400kb
input:
498 498 1951 289 275 304 352 50 441 95 466 432 162 324 216 367 399 413 154 163 345 290 127 450 195 437 41 326 421 236 299 248 449 60 233 31 183 278 228 184 444 384 448 135 462 39 486 215 123 136 120 12 200 182 416 475 292 180 40 381 334 324 310 113 429 177 398 393 447 67 350 112 46 133 23 205 218 33...
output:
136 381 233 255 416 173 137 39 416 137 100 136 44 416 136 151 262 173 185 173 402 44 151 137 311 137 154 198 151 136 416 68 44 185 11 198 327 475 416 416 334 136 402 262 255 100 475 44 100 475 151 107 39 381 68 68 173 173 173 173 262 11 416 39 136 173 398 446 255 475 260 100 416 137 152 262 311 352 ...
result:
ok Accepted.
Test #33:
score: 0
Accepted
time: 128ms
memory: 91340kb
input:
498 499 2728 88 127 472 81 109 272 124 323 459 371 316 200 321 29 306 46 458 36 95 143 148 205 207 308 252 440 39 74 131 100 237 277 298 341 16 473 349 492 83 461 98 382 17 13 295 198 65 83 165 426 127 412 413 327 237 268 183 211 207 255 221 41 128 433 100 217 40 9 151 64 426 360 189 322 209 26 290 ...
output:
-1
result:
ok Accepted.
Test #34:
score: 0
Accepted
time: 127ms
memory: 73636kb
input:
498 500 285 165 321 87 3 184 139 75 133 257 406 187 14 396 96 323 248 63 165 69 170 388 281 117 164 114 329 103 355 138 177 169 498 182 462 368 424 323 474 322 317 303 416 57 259 498 425 135 216 137 38 30 437 151 205 147 19 459 12 174 280 400 348 248 435 362 213 180 54 363 77 54 157 65 303 447 366 6...
output:
189 400 362 57 362 323 47 425 425 189 323 132 47 189 47 189 57 323 47 57 189 323 362 165 47 189 57 132 165 362 425 57 362 47 323 400 362 165 47 132 400 132 323 362 47 27 47 47 132 323 165 425 400 400 27 323 47 132 323 323 57 189 57 362 323 362 57 47 47 455 27 400 27 400 323 400 400 27 165 455 47 425...
result:
ok Accepted.
Test #35:
score: 0
Accepted
time: 114ms
memory: 71088kb
input:
499 500 371 4 44 100 459 299 107 478 284 421 197 56 90 381 198 305 237 137 260 451 188 381 435 230 458 354 76 100 157 431 198 133 394 181 340 221 198 180 15 269 386 287 330 378 152 198 129 274 318 139 38 150 385 11 352 114 428 408 154 248 44 206 76 264 56 35 222 457 194 196 272 494 443 96 453 439 43...
output:
222 294 157 76 294 76 294 222 76 44 76 294 157 381 294 381 428 294 76 76 381 222 157 381 157 381 294 428 222 381 381 157 294 44 76 76 157 76 76 428 157 428 294 44 294 157 157 76 381 157 428 157 157 157 76 157 44 428 381 157 428 44 428 76 157 381 157 157 157 381 381 76 76 294 44 76 381 157 381 428 38...
result:
ok Accepted.
Test #36:
score: 0
Accepted
time: 104ms
memory: 70528kb
input:
498 500 355 367 393 291 435 471 306 44 77 23 36 411 421 59 308 419 155 179 222 58 44 66 4 420 442 228 398 435 339 133 296 184 382 335 175 346 398 316 237 24 57 208 281 332 389 195 320 60 425 136 205 9 365 187 177 493 108 468 445 430 494 241 321 486 304 478 127 18 223 182 261 279 377 233 210 212 193 ...
output:
-1
result:
ok Accepted.
Test #37:
score: 0
Accepted
time: 122ms
memory: 80900kb
input:
500 498 215 80 358 454 116 72 463 139 277 370 436 202 220 16 188 1 213 38 59 494 217 497 424 426 135 35 302 419 26 326 499 209 10 311 315 451 285 54 60 161 103 168 413 393 104 234 308 434 39 442 49 306 374 311 158 342 287 74 14 199 102 285 51 379 459 411 125 101 210 84 321 369 111 45 334 65 471 143 ...
output:
466 397 75 199 93 258 35 240 8 19 159 84 341 459 177 50 438 447 186 192 91 193 469 274 239 122 91 447 41 175 41 258 54 215 24 60 366 447 379 285 392 5 177 24 199 328 6 15 54 201 407 481 91 8 287 366 8 87 175 25 156 481 366 397 466 215 177 35 287 24 392 240 201 199 24 330 79 15 400 24 253 348 91 414 ...
result:
ok Accepted.
Test #38:
score: 0
Accepted
time: 115ms
memory: 71492kb
input:
499 498 307 333 446 460 222 39 378 485 52 81 34 75 195 334 424 457 84 460 367 255 166 223 160 310 85 437 87 61 238 108 430 264 487 122 6 319 428 119 154 258 304 133 36 276 326 235 383 327 146 375 340 206 98 157 414 241 47 63 479 307 81 308 335 91 390 121 108 463 492 487 146 361 371 9 311 199 265 297...
output:
12 442 224 224 336 224 12 79 378 251 442 336 432 1 487 1 442 224 79 126 378 34 79 12 336 442 491 487 435 251 487 487 435 378 34 1 224 435 224 224 12 224 435 442 224 432 378 12 1 1 336 12 378 224 336 251 435 39 39 12 224 491 442 487 224 1 378 224 435 1 12 79 12 487 224 378 487 1 491 34 224 378 378 1 ...
result:
ok Accepted.
Test #39:
score: 0
Accepted
time: 99ms
memory: 71224kb
input:
498 499 314 282 244 343 470 265 268 88 151 423 412 198 242 421 306 203 225 297 471 63 170 290 497 83 91 132 248 11 395 127 81 387 98 422 222 108 122 29 375 419 297 144 324 151 58 96 345 330 475 177 68 144 28 35 448 394 371 328 124 141 279 231 67 208 340 10 403 298 77 170 127 274 378 305 439 81 442 3...
output:
406 144 406 144 144 144 144 144 144 406 146 406 146 144 144 144 144 144 144 144 155 144 146 144 144 144 406 144 144 144 144 406 144 144 144 144 144 144 144 144 144 406 146 144 144 144 155 469 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 144 406 155 144 144 144 155 144 406 ...
result:
ok Accepted.
Test #40:
score: 0
Accepted
time: 419ms
memory: 196800kb
input:
499 500 5000 262 245 206 378 294 422 331 197 13 210 57 31 239 117 278 155 209 272 182 479 200 209 178 150 371 388 286 42 104 405 356 494 171 235 362 305 361 269 34 20 256 137 233 425 346 311 170 69 76 319 168 110 366 162 305 265 199 194 107 182 59 157 48 243 153 435 469 22 226 54 360 187 72 363 293 ...
output:
475 206 96 249 384 7 358 150 192 287 357 343 494 324 308 249 435 435 5 40 466 182 292 486 262 182 455 471 81 2 81 7 497 82 176 75 486 220 192 227 365 342 350 463 428 51 104 96 260 494 102 202 230 249 426 343 96 323 192 270 475 388 479 217 205 180 287 455 96 412 407 233 131 343 453 90 345 136 114 475...
result:
ok Accepted.
Test #41:
score: 0
Accepted
time: 404ms
memory: 195364kb
input:
498 500 5000 306 1 215 389 341 416 374 34 262 125 476 288 444 90 342 85 215 31 472 463 2 111 325 349 59 275 435 49 448 82 497 167 233 428 407 232 155 109 365 49 322 318 381 10 84 226 422 345 388 168 206 304 301 282 275 47 38 489 210 442 332 118 339 125 393 67 210 421 270 388 380 354 358 352 310 228 ...
output:
243 36 34 465 414 441 359 206 355 379 438 434 44 205 482 88 243 96 372 285 348 93 240 167 498 469 131 457 348 453 298 400 175 394 93 73 449 243 149 4 193 374 372 221 205 127 416 410 70 416 31 187 175 143 44 348 364 113 355 439 419 8 31 242 379 283 446 387 94 187 285 457 245 179 263 387 217 127 235 3...
result:
ok Accepted.
Test #42:
score: 0
Accepted
time: 407ms
memory: 201928kb
input:
499 498 5000 395 382 498 86 410 99 157 411 263 304 133 323 163 150 111 220 38 124 305 157 398 491 269 82 9 376 91 239 285 185 370 362 121 456 414 63 306 140 454 183 206 60 417 483 34 482 138 412 358 173 75 346 477 324 429 59 10 486 202 412 426 246 360 267 200 439 394 363 77 348 320 187 442 428 120 5...
output:
-1
result:
ok Accepted.
Test #43:
score: 0
Accepted
time: 399ms
memory: 196784kb
input:
499 499 5000 56 232 281 262 375 216 390 313 244 105 298 227 349 160 115 400 455 98 147 463 25 371 97 131 255 345 187 342 93 207 207 432 330 216 301 346 415 377 166 265 399 495 94 276 354 139 74 50 230 385 42 480 276 457 419 239 264 97 413 157 436 401 154 203 284 425 414 389 358 93 60 308 285 259 144...
output:
147 421 181 74 329 94 291 94 85 194 329 431 109 371 293 91 112 298 358 33 313 431 294 296 204 204 448 313 293 358 161 329 313 43 85 161 298 206 169 293 291 431 293 283 343 303 336 493 348 147 423 348 112 33 226 448 236 277 236 109 293 378 182 85 109 194 109 348 493 313 431 28 182 456 293 313 493 371...
result:
ok Accepted.
Test #44:
score: 0
Accepted
time: 414ms
memory: 194552kb
input:
498 498 5000 466 442 188 316 306 215 336 277 11 225 2 23 426 316 396 299 463 201 280 428 288 440 104 398 238 363 341 6 289 106 142 49 192 481 4 195 323 278 185 213 461 475 465 317 324 465 68 187 434 491 222 268 141 334 72 108 61 360 321 471 498 18 166 206 396 377 96 127 5 91 213 456 29 286 191 224 2...
output:
448 226 341 237 376 351 457 376 435 482 374 414 457 377 71 127 401 482 416 91 67 373 137 376 236 91 482 44 416 265 329 101 359 265 184 405 448 351 461 341 385 329 416 101 127 461 373 107 414 156 184 176 416 341 150 70 150 384 416 70 46 265 46 137 236 114 226 377 376 91 137 384 341 439 482 176 482 46...
result:
ok Accepted.
Test #45:
score: 0
Accepted
time: 99ms
memory: 68808kb
input:
498 500 367 378 138 146 248 403 496 200 459 400 75 23 277 418 16 101 24 277 362 384 408 320 208 441 46 361 25 85 303 278 288 337 425 24 114 56 344 346 124 128 250 75 9 193 130 114 360 273 250 68 268 310 145 468 287 283 469 225 319 24 400 212 378 135 354 280 311 1 90 208 357 280 56 403 321 411 455 47...
output:
453 403 400 75 403 400 8 24 400 307 75 357 8 250 24 24 330 453 51 400 307 250 8 330 453 24 8 24 24 24 75 250 453 400 8 491 24 453 24 24 400 403 24 24 400 307 24 491 8 51 51 400 51 24 51 24 453 453 400 400 24 453 400 403 24 8 400 400 400 75 307 24 75 400 51 400 75 250 250 24 330 250 24 24 400 400 24 ...
result:
ok Accepted.
Test #46:
score: 0
Accepted
time: 109ms
memory: 73380kb
input:
498 498 294 286 177 26 389 64 73 369 155 345 299 409 106 94 9 286 191 199 354 43 307 107 441 258 222 264 129 456 23 462 275 344 156 193 445 401 360 215 267 33 442 209 465 170 1 257 189 418 15 324 377 175 120 486 498 303 353 30 172 104 43 344 76 126 325 264 455 445 310 47 12 420 381 394 331 391 233 1...
output:
416 238 471 28 179 365 471 28 365 238 238 28 498 371 416 371 416 28 76 471 177 177 28 286 416 179 471 365 76 238 371 179 76 177 76 371 365 365 238 76 76 238 76 177 371 471 286 371 471 383 179 76 177 177 371 28 371 498 498 286 286 498 416 498 471 177 179 177 177 286 498 286 498 416 416 383 28 365 286...
result:
ok Accepted.
Test #47:
score: 0
Accepted
time: 137ms
memory: 81172kb
input:
498 500 214 246 323 132 465 29 71 436 107 95 214 163 281 487 35 388 133 469 148 250 240 486 135 45 144 311 160 461 127 372 283 254 127 252 389 276 441 94 194 115 98 209 127 411 242 99 50 180 47 124 107 483 44 175 272 229 159 176 41 9 206 477 397 302 108 11 318 362 391 356 363 417 391 274 65 71 309 1...
output:
146 213 213 147 146 146 146 394 147 147 146 276 147 147 276 394 146 394 213 213 146 276 213 213 146 147 146 394 213 394 276 276 147 276 394 276 146 147 276 276 394 146 213 213 147 276 146 213 146 394 146 394 146 276 213 146 146 394 147 394 146 213 146 394 394 146 276 213 213 147 394 146 147 276 146 ...
result:
ok Accepted.
Subtask #5:
score: 0
Time Limit Exceeded
Dependency #3:
100%
Accepted
Dependency #4:
100%
Accepted
Test #48:
score: 0
Time Limit Exceeded
input:
1999 1999 16990 734 609 971 297 1864 1528 1995 858 1223 411 1800 580 451 1384 800 866 1709 422 740 1381 1402 431 614 526 249 531 406 228 1589 456 1357 1731 852 869 557 1681 1072 632 1695 358 1686 186 1706 313 189 1115 907 1051 1645 1854 1794 1639 1857 1859 496 660 1784 578 311 100 1430 765 330 1319 ...
output:
result:
Subtask #6:
score: 0
Skipped
Dependency #1:
0%