QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#217613 | #7177. Many Many Cycles | Lain | WA | 174ms | 4424kb | C++20 | 2.8kb | 2023-10-17 02:37:33 | 2023-10-17 02:37:34 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
template<class T>
struct RMQ {
vector<vector<T>> jmp;
RMQ(const vector<T>& V) : jmp(1, V) {
for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) {
jmp.emplace_back(sz(V) - pw * 2 + 1);
rep(j,0,sz(jmp[k]))
jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]);
}
}
T query(int a, int b) {
assert(a < b); // or return inf if a == b
int dep = 31 - __builtin_clz(b - a);
return min(jmp[dep][a], jmp[dep][b - (1 << dep)]);
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
struct edge {
int u, v, w, is_span;
int to(int x) {
return u^v^x;
}
};
int n, m;
cin >> n >> m;
vector<edge> edges;
edges.reserve(m);
vector<vi> g(n);
rep(i, 0, m) {
int u, v, w;
cin >> u >> v >> w;
u--,v--;
g[u].push_back(sz(edges));
g[v].push_back(sz(edges));
edges.push_back({u,v,w,0});
}
int comp_num = 0, T = 0;
vi vis(n), comp(n), dep(n), time(n), path, ret;
vector<ll> dist(n);
auto dfs = [&](auto& self, int s)->void {
time[s] = T++;
vis[s] = 1;
comp[s] = comp_num;
for (auto& e : g[s]) {
int u = edges[e].to(s);
if (vis[u]) continue;
path.push_back(s);
ret.push_back(time[s]);
edges[e].is_span = 1;
dist[u] = dist[s] + edges[e].w;
dep[u] = dep[s]+1;
self(self, u);
}
};
rep(i, 0, n) {
if (!vis[i]) {
dfs(dfs, i);
comp_num++;
}
}
RMQ rmq(ret);
auto lca = [&](int x, int y)->int {
assert(comp[x] == comp[y]);
if (x == y) return x;
tie(x, y) = minmax(time[x], time[y]);
return path[rmq.query(x, y)];
};
vi not_span;
rep(i, 0, m) if (!edges[i].is_span) not_span.push_back(i);
ll ans = 0;
rep(_i, 0, sz(not_span)) {
int i = not_span[_i];
auto& [u,v, w, _] = edges[i];
if (dep[u] > dep[v]) swap(u, v); // u above v
// Simple cycle
ans = __gcd(ans, dist[v] - dist[u] + w);
// xored
rep(_j, _i+1, sz(not_span)) {
int j = not_span[_j];
auto& [a, b, w1, _] = edges[j];
if (comp[a] != comp[u]) continue; // not in the same component, ignore
if (dep[a] > dep[b]) swap(a, b); // a above b
if (dep[b] <= dep[u]) continue; // no intersection, b above u
int upper = dep[a] < dep[u] ? a : u;
int lower = dep[a] > dep[u] ? a : u;
if (lca(upper, lower) != upper) continue; // no shared edges
int l = lca(v, b);
if (dep[l] <= dep[lower]) continue;
ans = __gcd(ans, 2*(dist[l] - dist[lower]));
}
}
cout << ans << '\n';
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3492kb
input:
4 4 1 2 1 2 3 1 3 4 1 4 1 1
output:
4
result:
ok answer is '4'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
4 5 1 2 1 1 3 2 1 4 1 2 3 1 3 4 1
output:
4
result:
ok answer is '4'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
20 50 1 2 8 1 3 1 3 4 5 3 5 9 3 6 5 6 7 6 7 8 8 2 9 2 8 10 3 8 11 7 8 12 5 3 13 4 7 14 3 6 15 7 9 16 6 8 17 7 16 18 9 16 19 3 18 20 10 11 3 2 17 1 1 16 2 2 15 1 1 10 3 2 9 1 2 19 2 1 6 1 2 7 3 1 17 3 2 15 3 2 8 6 2 5 1 2 8 1 2 12 1 1 12 7 1 4 1 2 18 2 1 11 7 1 14 1 1 18 1 1 18 9 1 10 6 1 14 3 2 20 2...
output:
2
result:
ok answer is '2'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3448kb
input:
20 50 1 2 18468 1 3 26501 3 4 15725 3 5 29359 3 6 24465 6 7 28146 7 8 16828 2 9 492 8 10 11943 8 11 5437 8 12 14605 3 13 154 7 14 12383 6 15 18717 9 16 19896 8 17 21727 16 18 11539 16 19 19913 18 20 26300 11 3 2 17 1 1 16 2 2 15 1 1 10 3 2 9 1 2 19 2 1 6 1 2 7 3 1 17 3 2 15 3 2 8 6 2 5 1 2 8 1 2 12 ...
output:
1
result:
ok answer is '1'
Test #5:
score: 0
Accepted
time: 1ms
memory: 3464kb
input:
100 150 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 11...
output:
3
result:
ok answer is '3'
Test #6:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
100 130 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 11...
output:
7
result:
ok answer is '7'
Test #7:
score: 0
Accepted
time: 1ms
memory: 3468kb
input:
100 200 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 11...
output:
4
result:
ok answer is '4'
Test #8:
score: 0
Accepted
time: 1ms
memory: 3504kb
input:
100 190 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 11...
output:
2
result:
ok answer is '2'
Test #9:
score: 0
Accepted
time: 2ms
memory: 3604kb
input:
1000 1500 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 ...
output:
3
result:
ok answer is '3'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3596kb
input:
1000 1500 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 ...
output:
1
result:
ok answer is '1'
Test #11:
score: 0
Accepted
time: 3ms
memory: 3680kb
input:
1000 1600 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 ...
output:
1
result:
ok answer is '1'
Test #12:
score: 0
Accepted
time: 1ms
memory: 3568kb
input:
100 190 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 11...
output:
4
result:
ok answer is '4'
Test #13:
score: 0
Accepted
time: 34ms
memory: 3764kb
input:
1000 3000 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 ...
output:
2
result:
ok answer is '2'
Test #14:
score: 0
Accepted
time: 2ms
memory: 3632kb
input:
1000 1400 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 ...
output:
1
result:
ok answer is '1'
Test #15:
score: 0
Accepted
time: 2ms
memory: 3644kb
input:
1000 1500 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 ...
output:
2
result:
ok answer is '2'
Test #16:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
1000 1500 1 2 184676335 1 3 191705725 1 4 293606963 1 5 57078146 2 6 168279962 6 7 29961943 5 8 54392392 5 9 39020154 5 10 123837422 7 11 197199896 3 12 217274772 7 13 18709913 6 14 263007036 11 15 287053812 3 16 303347674 9 17 151417712 17 18 68705548 15 19 326652758 12 20 128598724 2 21 275290779 ...
output:
8
result:
ok answer is '8'
Test #17:
score: 0
Accepted
time: 3ms
memory: 3752kb
input:
2000 2500 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
12
result:
ok answer is '12'
Test #18:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
2000 2500 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
2
result:
ok answer is '2'
Test #19:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
2000 2500 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
13
result:
ok answer is '13'
Test #20:
score: 0
Accepted
time: 2ms
memory: 3788kb
input:
2000 2500 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
1
result:
ok answer is '1'
Test #21:
score: 0
Accepted
time: 7ms
memory: 3768kb
input:
2000 3000 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
3
result:
ok answer is '3'
Test #22:
score: 0
Accepted
time: 7ms
memory: 3804kb
input:
2000 3000 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
1
result:
ok answer is '1'
Test #23:
score: 0
Accepted
time: 2ms
memory: 3752kb
input:
2000 2500 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
1
result:
ok answer is '1'
Test #24:
score: 0
Accepted
time: 17ms
memory: 3836kb
input:
2000 3500 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
2
result:
ok answer is '2'
Test #25:
score: 0
Accepted
time: 25ms
memory: 3844kb
input:
2000 4000 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
4
result:
ok answer is '4'
Test #26:
score: 0
Accepted
time: 2ms
memory: 3784kb
input:
2000 2300 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
1
result:
ok answer is '1'
Test #27:
score: 0
Accepted
time: 25ms
memory: 3900kb
input:
3000 5000 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
1
result:
ok answer is '1'
Test #28:
score: 0
Accepted
time: 5ms
memory: 3956kb
input:
3000 3700 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
13
result:
ok answer is '13'
Test #29:
score: 0
Accepted
time: 4ms
memory: 3928kb
input:
3000 3700 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
1
result:
ok answer is '1'
Test #30:
score: 0
Accepted
time: 56ms
memory: 4424kb
input:
5000 8000 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
3
result:
ok answer is '3'
Test #31:
score: 0
Accepted
time: 56ms
memory: 4420kb
input:
5000 8000 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
1
result:
ok answer is '1'
Test #32:
score: 0
Accepted
time: 30ms
memory: 4256kb
input:
5000 7200 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
5
result:
ok answer is '5'
Test #33:
score: 0
Accepted
time: 26ms
memory: 4280kb
input:
5000 7200 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
1
result:
ok answer is '1'
Test #34:
score: 0
Accepted
time: 56ms
memory: 4292kb
input:
5000 8000 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
6
result:
ok answer is '6'
Test #35:
score: 0
Accepted
time: 51ms
memory: 4252kb
input:
5000 8000 1 2 22794613 1 3 23670271 1 4 36254735 1 5 7068116 2 6 20774480 6 7 3707773 5 8 6740416 5 9 4815222 5 10 15296810 7 11 24351908 3 12 26824656 7 13 2326259 6 14 32470002 11 15 35443314 3 16 37448596 9 17 18691706 17 18 8500660 15 19 40337666 12 20 15876730 2 21 33971565 11 22 3767381 17 23 ...
output:
2
result:
ok answer is '2'
Test #36:
score: 0
Accepted
time: 173ms
memory: 4212kb
input:
5000 10000 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 205804...
output:
4
result:
ok answer is '4'
Test #37:
score: 0
Accepted
time: 174ms
memory: 4280kb
input:
5000 10000 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 205804...
output:
2
result:
ok answer is '2'
Test #38:
score: 0
Accepted
time: 7ms
memory: 4232kb
input:
5000 6000 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
7
result:
ok answer is '7'
Test #39:
score: 0
Accepted
time: 8ms
memory: 4236kb
input:
5000 6000 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
1
result:
ok answer is '1'
Test #40:
score: 0
Accepted
time: 9ms
memory: 4268kb
input:
5000 6000 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
2
result:
ok answer is '2'
Test #41:
score: 0
Accepted
time: 2ms
memory: 4288kb
input:
5000 6000 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
9
result:
ok answer is '9'
Test #42:
score: 0
Accepted
time: 17ms
memory: 4296kb
input:
5000 6666 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
9
result:
ok answer is '9'
Test #43:
score: 0
Accepted
time: 17ms
memory: 4264kb
input:
5000 6666 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
1
result:
ok answer is '1'
Test #44:
score: 0
Accepted
time: 7ms
memory: 4236kb
input:
5000 6000 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
12345
result:
ok answer is '12345'
Test #45:
score: 0
Accepted
time: 7ms
memory: 4268kb
input:
5000 6000 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
997
result:
ok answer is '997'
Test #46:
score: 0
Accepted
time: 7ms
memory: 4232kb
input:
5000 6000 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
1
result:
ok answer is '1'
Test #47:
score: 0
Accepted
time: 2ms
memory: 4192kb
input:
5000 4999 1 2 4216811 1 3 4386257 1 4 6720587 1 5 1328886 2 6 3846518 6 7 694803 5 8 1271800 5 9 889810 5 10 2840518 7 11 4515600 3 12 4968300 7 13 446045 6 14 6013208 11 15 6568096 3 16 6933598 9 17 3459860 17 18 1591452 15 19 7479694 12 20 2940576 2 21 6277391 11 22 714171 17 23 95771 2 24 2058041...
output:
0
result:
ok answer is '0'
Test #48:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
6 6 1 2 999999999 2 3 999999999 3 4 999999999 4 5 999999999 5 6 999999999 6 1 999999999
output:
5999999994
result:
ok answer is '5999999994'
Test #49:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
6 6 1 2 6 2 3 6 3 1 6 4 5 15 5 6 7 6 4 8
output:
6
result:
ok answer is '6'
Test #50:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
1 0
output:
0
result:
ok answer is '0'
Test #51:
score: 0
Accepted
time: 0ms
memory: 3444kb
input:
4 5 1 2 1 3 4 1 2 3 1 1 4 1 1 3 1
output:
1
result:
ok answer is '1'
Test #52:
score: 0
Accepted
time: 1ms
memory: 3452kb
input:
6 6 1 2 1 1 3 1 3 4 1 1 4 1 2 3 1 5 1 1
output:
1
result:
ok answer is '1'
Test #53:
score: 0
Accepted
time: 1ms
memory: 3548kb
input:
9 10 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 1 8 1 4 9 1 6 9 1
output:
4
result:
ok answer is '4'
Test #54:
score: 0
Accepted
time: 1ms
memory: 3488kb
input:
6 7 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 1 6 1 3 6 1
output:
2
result:
ok answer is '2'
Test #55:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
33 36 2 22 1 12 18 1 27 28 1 9 19 1 26 27 1 6 21 1 15 16 1 2 3 1 7 24 1 3 12 1 4 23 1 28 29 1 5 14 1 29 30 1 1 10 1 11 13 1 6 13 1 16 25 1 14 21 1 4 16 1 10 19 1 10 11 1 5 15 1 1 8 1 3 20 1 7 13 1 25 26 1 29 31 1 17 23 1 8 18 1 12 24 1 25 30 1 31 32 1 17 20 1 15 22 1 9 18 1
output:
3
result:
ok answer is '3'
Test #56:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
33 35 10 13 1 6 13 1 9 19 1 5 15 1 29 31 1 2 3 1 4 16 1 3 20 1 7 13 1 31 32 1 12 24 1 2 22 1 17 23 1 26 27 1 17 20 1 16 25 1 3 12 1 28 29 1 1 8 1 12 18 1 27 28 1 14 21 1 10 19 1 25 26 1 5 14 1 15 16 1 9 18 1 4 23 1 25 30 1 1 10 1 8 18 1 7 24 1 29 30 1 6 21 1 15 22 1
output:
1
result:
ok answer is '1'
Test #57:
score: 0
Accepted
time: 1ms
memory: 3876kb
input:
2000 2000 1036 1254 1 1453 1496 1 342 1815 1 186 346 1 840 1555 1 138 1503 1 416 1376 1 660 1253 1 1279 1799 1 209 1554 1 624 1278 1 792 884 1 333 1703 1 393 894 1 551 1192 1 1705 1805 1 302 930 1 115 1384 1 151 1156 1 71 209 1 82 1637 1 858 1854 1 19 1798 1 348 703 1 1692 1744 1 261 1029 1 143 1631...
output:
2000
result:
ok answer is '2000'
Test #58:
score: 0
Accepted
time: 1ms
memory: 3836kb
input:
1820 1872 677 1254 1 114 163 1 1751 1815 1 532 1640 1 290 380 1 253 1429 1 174 1163 1 1005 1431 1 521 1324 1 37 1553 1 369 1764 1 658 1170 1 1456 1574 1 224 663 1 752 1460 1 128 441 1 831 1013 1 730 1583 1 500 983 1 374 1274 1 1394 1478 1 422 1223 1 1310 1632 1 1133 1508 1 914 1258 1 151 907 1 221 2...
output:
18
result:
ok answer is '18'
Test #59:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
1521 1584 1138 1283 1 95 542 1 137 1042 1 1043 1390 1 147 1396 1 382 709 1 651 828 1 909 1124 1 286 1485 1 31 171 1 925 1254 1 360 501 1 900 1229 1 69 1358 1 166 199 1 633 1178 1 310 1390 1 679 1482 1 844 1333 1 761 1208 1 38 1512 1 449 875 1 13 1467 1 77 217 1 622 736 1 45 1163 1 365 1346 1 106 108...
output:
12
result:
ok answer is '12'
Test #60:
score: 0
Accepted
time: 1ms
memory: 3644kb
input:
1433 1467 43 1268 1 90 1143 1 237 271 1 444 1375 1 232 1407 1 1026 1139 1 861 943 1 981 1003 1 77 1229 1 416 966 1 606 1370 1 351 438 1 687 1379 1 1030 1186 1 1373 1428 1 715 762 1 553 1426 1 238 1012 1 120 618 1 345 857 1 827 1118 1 548 1085 1 245 333 1 82 910 1 202 570 1 80 781 1 666 797 1 122 102...
output:
9
result:
ok answer is '9'
Test #61:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
1569 1625 1043 1553 1 57 369 1 481 1231 1 99 227 1 113 262 1 239 354 1 175 887 1 819 1230 1 27 115 1 76 820 1 1086 1498 1 482 1193 1 1299 1447 1 570 604 1 121 508 1 100 208 1 77 572 1 52 1296 1 198 639 1 103 945 1 256 381 1 745 1173 1 1033 1350 1 13 1414 1 233 1399 1 402 1417 1 1394 1441 1 206 623 1...
output:
5
result:
ok answer is '5'
Test #62:
score: 0
Accepted
time: 1ms
memory: 3600kb
input:
1035 1072 448 654 1 201 211 1 139 650 1 224 255 1 430 883 1 494 517 1 199 999 1 717 763 1 661 813 1 145 574 1 68 908 1 626 990 1 7 805 1 54 875 1 600 968 1 279 462 1 335 543 1 266 665 1 598 676 1 177 447 1 790 1034 1 273 909 1 475 814 1 464 973 1 210 560 1 290 905 1 650 708 1 288 994 1 10 183 1 261 ...
output:
8
result:
ok answer is '8'
Test #63:
score: 0
Accepted
time: 1ms
memory: 3456kb
input:
162 198 41 83 1 15 121 1 29 76 1 62 75 1 78 114 1 58 80 1 5 75 1 85 119 1 45 137 1 3 56 1 149 156 1 46 63 1 79 107 1 125 150 1 33 78 1 43 149 1 27 87 1 20 33 1 13 136 1 60 90 1 60 110 1 30 97 1 102 152 1 25 31 1 6 79 1 24 67 1 16 78 1 68 115 1 77 78 1 103 124 1 117 161 1 117 139 1 55 67 1 19 146 1 4...
output:
3
result:
ok answer is '3'
Test #64:
score: 0
Accepted
time: 1ms
memory: 3732kb
input:
1894 1932 384 1664 1 1204 1508 1 733 1583 1 818 1515 1 879 1799 1 197 1165 1 657 919 1 559 1893 1 241 1104 1 347 1283 1 516 916 1 179 1041 1 305 477 1 1116 1135 1 1254 1561 1 280 742 1 269 975 1 34 862 1 1033 1659 1 74 382 1 307 1600 1 99 1553 1 1298 1565 1 955 1579 1 308 478 1 947 1595 1 1686 1793 ...
output:
7
result:
ok answer is '7'
Test #65:
score: 0
Accepted
time: 30ms
memory: 3548kb
input:
63 1953 24 25 1 30 53 1 16 28 1 20 36 1 34 51 1 33 52 1 3 11 1 9 35 1 28 52 1 52 54 1 22 51 1 33 46 1 2 45 1 35 43 1 4 48 1 4 35 1 2 7 1 26 59 1 21 35 1 21 43 1 9 58 1 37 63 1 7 26 1 17 32 1 7 11 1 34 56 1 6 54 1 18 62 1 33 44 1 15 52 1 50 53 1 17 46 1 12 42 1 9 31 1 9 11 1 35 47 1 1 13 1 21 42 1 26...
output:
1
result:
ok answer is '1'
Test #66:
score: 0
Accepted
time: 28ms
memory: 3640kb
input:
89 1939 29 62 1 14 25 1 5 60 1 24 26 1 1 8 1 3 68 1 47 85 1 41 81 1 47 55 1 22 75 1 20 37 1 42 87 1 46 53 1 48 55 1 54 72 1 61 66 1 7 43 1 70 74 1 63 89 1 29 51 1 21 56 1 18 49 1 20 31 1 14 34 1 22 85 1 75 86 1 52 68 1 12 32 1 44 55 1 41 42 1 37 82 1 36 82 1 5 67 1 52 74 1 5 18 1 35 40 1 14 60 1 11 ...
output:
1
result:
ok answer is '1'
Test #67:
score: 0
Accepted
time: 20ms
memory: 3560kb
input:
409 1944 69 134 1 162 172 1 50 327 1 3 17 1 152 256 1 19 302 1 246 371 1 289 394 1 228 376 1 210 270 1 318 336 1 352 405 1 171 324 1 21 398 1 70 236 1 68 349 1 316 344 1 84 386 1 223 344 1 125 223 1 293 327 1 88 253 1 39 165 1 151 395 1 201 322 1 68 403 1 336 383 1 215 256 1 73 138 1 5 399 1 260 268...
output:
1
result:
ok answer is '1'
Test #68:
score: 0
Accepted
time: 15ms
memory: 3700kb
input:
509 1828 245 248 1 384 386 1 127 261 1 260 480 1 437 466 1 127 382 1 158 476 1 482 498 1 241 375 1 159 216 1 232 408 1 74 270 1 32 293 1 126 249 1 59 445 1 146 291 1 129 234 1 81 164 1 243 437 1 258 262 1 229 320 1 126 185 1 118 423 1 221 488 1 185 204 1 220 227 1 96 472 1 112 149 1 106 432 1 46 100...
output:
2
result:
ok answer is '2'
Test #69:
score: 0
Accepted
time: 1ms
memory: 3840kb
input:
2000 1999 1552 1932 1 553 1152 1 1006 1967 1 606 1381 1 1549 1775 1 1283 1992 1 994 1000 1 367 1864 1 1047 1989 1 475 1284 1 1033 1688 1 827 1786 1 746 1018 1 651 756 1 73 1178 1 307 539 1 114 1924 1 653 667 1 693 1087 1 222 1656 1 241 1841 1 165 1725 1 433 476 1 66 1099 1 169 1490 1 609 1257 1 506 ...
output:
1440
result:
ok answer is '1440'
Test #70:
score: 0
Accepted
time: 1ms
memory: 3708kb
input:
1302 1302 893 1045 1 149 798 1 202 1034 1 252 789 1 269 920 1 915 989 1 96 496 1 1142 1302 1 647 868 1 54 1127 1 161 704 1 128 1294 1 51 718 1 325 825 1 423 798 1 344 809 1 504 1070 1 548 756 1 276 1116 1 8 41 1 782 1294 1 602 685 1 137 976 1 315 1028 1 75 562 1 36 1208 1 20 302 1 383 1080 1 62 392 ...
output:
42
result:
ok answer is '42'
Test #71:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
1932 1989 390 911 1 1384 1761 1 679 791 1 931 1855 1 315 1346 1 201 331 1 167 1560 1 72 1206 1 255 1838 1 1777 1854 1 693 1869 1 1225 1343 1 588 825 1 904 1120 1 413 773 1 853 1521 1 884 924 1 628 638 1 370 1080 1 1004 1821 1 342 817 1 1315 1448 1 289 352 1 1389 1730 1 921 1602 1 880 1307 1 164 263 ...
output:
17
result:
ok answer is '17'
Test #72:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
561 572 290 330 1 81 158 1 158 166 1 501 548 1 387 482 1 54 121 1 521 535 1 106 397 1 263 466 1 230 520 1 332 400 1 55 374 1 182 209 1 138 219 1 154 506 1 494 510 1 45 346 1 190 421 1 290 383 1 56 361 1 123 157 1 380 538 1 345 525 1 225 318 1 82 356 1 40 340 1 245 451 1 420 520 1 470 556 1 279 347 1...
output:
13
result:
ok answer is '13'
Test #73:
score: 0
Accepted
time: 1ms
memory: 3524kb
input:
573 585 96 357 1 358 495 1 136 375 1 200 538 1 1 112 1 170 524 1 125 273 1 189 572 1 525 562 1 24 443 1 152 173 1 224 250 1 470 572 1 76 299 1 289 371 1 161 561 1 269 435 1 114 122 1 225 442 1 65 175 1 207 319 1 73 469 1 6 327 1 144 357 1 389 557 1 256 534 1 398 413 1 87 413 1 519 567 1 312 353 1 40...
output:
1
result:
ok answer is '1'
Test #74:
score: 0
Accepted
time: 1ms
memory: 3484kb
input:
230 246 13 198 1 31 100 1 54 181 1 10 211 1 210 218 1 151 178 1 175 228 1 66 164 1 15 81 1 156 214 1 36 200 1 154 228 1 73 84 1 57 210 1 127 144 1 81 167 1 131 154 1 40 143 1 86 157 1 48 58 1 208 230 1 164 230 1 4 132 1 22 159 1 67 138 1 63 78 1 171 184 1 69 121 1 51 209 1 9 38 1 111 167 1 65 75 1 1...
output:
6
result:
ok answer is '6'
Test #75:
score: 0
Accepted
time: 1ms
memory: 3516kb
input:
436 468 328 330 1 46 78 1 219 400 1 165 329 1 278 391 1 45 387 1 166 402 1 66 213 1 102 358 1 185 368 1 91 136 1 33 378 1 73 102 1 111 150 1 95 405 1 150 402 1 6 223 1 119 351 1 110 381 1 178 407 1 175 212 1 379 416 1 153 310 1 198 241 1 259 319 1 114 177 1 66 341 1 26 354 1 302 364 1 232 385 1 175 ...
output:
9
result:
ok answer is '9'
Test #76:
score: -100
Wrong Answer
time: 1ms
memory: 3612kb
input:
2000 714 13 198 1 31 100 1 54 181 1 10 211 1 210 218 1 151 178 1 175 228 1 66 164 1 15 81 1 156 214 1 36 200 1 154 228 1 73 84 1 57 210 1 127 144 1 81 167 1 131 154 1 40 143 1 86 157 1 48 58 1 208 230 1 164 230 1 4 132 1 22 159 1 67 138 1 63 78 1 171 184 1 69 121 1 51 209 1 9 38 1 111 167 1 65 75 1 ...
output:
1
result:
wrong answer expected '3', found '1'