QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#233121 | #7177. Many Many Cycles | ikefumy | WA | 183ms | 5732kb | C++20 | 5.6kb | 2023-10-31 13:41:21 | 2023-10-31 13:41:21 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define db double
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define ti3 tuple<int,int,int>
#define int128 __int128_t
#define pii128 pair<int128,int128>
const int inf = 1 << 30;
const ll linf = 1e18;
const ll mod = 1e9 + 7;
const db EPS = 1e-10;
const db pi = acos(-1);
template<class T> bool chmin(T& x, T y){
if(x > y) {
x = y;
return true;
} else return false;
}
template<class T> bool chmax(T& x, T y){
if(x < y) {
x = y;
return true;
} else return false;
}
// overload macro
#define CAT( A, B ) A ## B
#define SELECT( NAME, NUM ) CAT( NAME, NUM )
#define GET_COUNT( _1, _2, _3, _4, _5, _6 /* ad nauseam */, COUNT, ... ) COUNT
#define VA_SIZE( ... ) GET_COUNT( __VA_ARGS__, 6, 5, 4, 3, 2, 1 )
#define VA_SELECT( NAME, ... ) SELECT( NAME, VA_SIZE(__VA_ARGS__) )(__VA_ARGS__)
// rep(overload)
#define rep( ... ) VA_SELECT(rep, __VA_ARGS__)
#define rep2(i, n) for (int i = 0; i < int(n); i++)
#define rep3(i, a, b) for (int i = a; i < int(b); i++)
#define rep4(i, a, b, c) for (int i = a; i < int(b); i += c)
// repll(overload)
#define repll( ... ) VA_SELECT(repll, __VA_ARGS__)
#define repll2(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repll3(i, a, b) for (ll i = a; i < (ll)(b); i++)
#define repll4(i, a, b, c) for (ll i = a; i < (ll)(b); i += c)
// rrep(overload)
#define rrep( ... ) VA_SELECT(rrep, __VA_ARGS__)
#define rrep2(i, n) for (int i = n - 1; i >= 0; i--)
#define rrep3(i, a, b) for (int i = b - 1; i >= a; i--)
#define rrep4(i, a, b, c) for (int i = b - 1; i >= a; i -= c)
// rrepll(overload)
#define rrepll( ... ) VA_SELECT(rrepll, __VA_ARGS__)
#define rrepll2(i, n) for (ll i = (ll)(n) - 1; i >= 0ll; i--)
#define rrepll3(i, a, b) for (ll i = b - 1; i >= (ll)(a); i--)
#define rrepll4(i, a, b, c) for (ll i = b - 1; i >= (ll)(a); i -= c)
// for_earh
#define fore(e, v) for (auto&& e : v)
// vector
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
struct LCA{
int N;
int logn;
vector<vector<int>> G;
vector<vector<int>> par;
vector<int> depth, used;
LCA(int n) : N(n), logn(0), G(n + 1), depth(n + 1), used(n + 1) {
while((1 << logn) <= N) logn++;
par = vector<vector<int>>(logn, vector<int>(n + 1));
}
void add_edge(int u, int v){
G[u].push_back(v);
G[v].push_back(u);
}
void dfs(int v, int p, int d){
par[0][v] = p;
depth[v] = d;
used[v] = true;
for(auto& u : G[v]){
if(p == u) continue;
dfs(u, v, d + 1);
}
}
void setting(){
for (int i = 1; i <= N; i++) {
if (used[i]) continue;
dfs(1, -1, 0);
}
for(int i = 1; i < logn; i++){
for(int j = 1; j <= N; j++){
if(par[i - 1][j] < 0) par[i][j] = -1;
else par[i][j] = par[i - 1][par[i - 1][j]];
}
}
}
int get_lca(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int d = depth[u] - depth[v];
for(int i = 0; i < logn; i++){
if(d >> i & 1) u = par[i][u];
}
if(u == v) return u;
for(int i = logn - 1; i >= 0; i--){
if(par[i][u] != par[i][v]){
u = par[i][u];
v = par[i][v];
}
}
return par[0][u];
}
int get_len(int u, int v) {
int cp = get_lca(u, v);
return depth[u] + depth[v] - depth[cp] * 2;
}
};
int N, M, par[5010];
ll depth[5010], g;
vector<pil> G[5010];
vector<pil> TG[5010];
vector<pil> rem[5010];
bool used[5010];
LCA lca(0);
void dfs(int v, ll d) {
used[v] = true;
depth[v] = d;
for (auto& [u, w] : G[v]) {
if (used[u]) {
if (u != par[v]) {
rem[v].emplace_back(u, w);
rem[u].emplace_back(v, w);
}
continue;
}
par[u] = v;
TG[v].emplace_back(u, w);
TG[u].emplace_back(v, w);
lca.add_edge(u, v);
dfs(u, d + w);
}
}
void make_ans(int v, int p) {
used[v] = true;
for (auto&& [u, w] : TG[v]) {
if (u == p) continue;
make_ans(u, v);
}
for (auto&& [u, w] : rem[v]) {
if (depth[u] > depth[v]) continue;
g = gcd(g, w + depth[v] - depth[u]);
int p = v;
while (true) {
for (auto&& [q, r] : rem[p]) {
if (depth[q] < depth[p]) continue;
if (max(u, v) == max(p, q) && min(u, v) == min(p, q)) continue;
ll len = w + r + depth[p] - depth[u];
len += depth[v] + depth[q] - 2 * depth[lca.get_lca(v, q)];
g = gcd(g, len);
}
if (p == u) break;
p = par[p];
}
}
}
int main() {
cin.tie(nullptr);
ios_base::sync_with_stdio(false);
cout << fixed << setprecision(20);
cin >> N >> M;
lca = LCA(N);
rep (i, M) {
int a, b, c;
cin >> a >> b >> c;
G[a].emplace_back(b, c);
G[b].emplace_back(a, c);
}
rep (i, 1, N + 1) {
if (used[i]) continue;
dfs(i, 0);
}
lca.setting();
rep (i, 1, N + 1) used[i] = false;
rep (i, 1, N + 1) {
if (used[i]) continue;
make_ans(i, 0);
}
cout << g << endl;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3796kb
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: 1ms
memory: 3960kb
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: 3928kb
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: 1ms
memory: 3928kb
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: 4000kb
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: 4216kb
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: 4004kb
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: 3988kb
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: 4136kb
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: 0ms
memory: 4176kb
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: 2ms
memory: 4288kb
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: 4140kb
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: 135ms
memory: 4344kb
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: 1ms
memory: 4124kb
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: 0ms
memory: 4184kb
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: 4476kb
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: 2ms
memory: 4496kb
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: 0ms
memory: 4472kb
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: 0ms
memory: 4368kb
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: 4656kb
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: 4ms
memory: 4472kb
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: 2ms
memory: 4500kb
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: 4656kb
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: 20ms
memory: 4800kb
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: 39ms
memory: 4600kb
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: 4372kb
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: 10ms
memory: 4840kb
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: 2ms
memory: 4756kb
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: 3ms
memory: 4744kb
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: 15ms
memory: 5436kb
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: 16ms
memory: 5524kb
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: 8ms
memory: 5352kb
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: 4ms
memory: 5328kb
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: 15ms
memory: 5732kb
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: 15ms
memory: 5524kb
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: 130ms
memory: 5704kb
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: 130ms
memory: 5664kb
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: 0ms
memory: 5168kb
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: 4ms
memory: 5204kb
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: 5ms
memory: 5240kb
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: 4ms
memory: 5220kb
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: 2ms
memory: 5336kb
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: 2ms
memory: 5256kb
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: 3ms
memory: 5232kb
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: 3ms
memory: 5384kb
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: 3ms
memory: 5248kb
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: 5040kb
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: 0ms
memory: 3896kb
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: 4184kb
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: 3972kb
input:
1 0
output:
0
result:
ok answer is '0'
Test #51:
score: 0
Accepted
time: 0ms
memory: 3916kb
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: 0ms
memory: 3892kb
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: 0ms
memory: 3956kb
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: 0ms
memory: 4144kb
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: 3984kb
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: 3904kb
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: 4780kb
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: 2ms
memory: 4448kb
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: 1ms
memory: 4400kb
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: 4280kb
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: 4572kb
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: 4228kb
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: 0ms
memory: 4156kb
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: 4628kb
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: 157ms
memory: 4144kb
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: 183ms
memory: 4520kb
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: 158ms
memory: 4340kb
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: 119ms
memory: 4360kb
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: 0ms
memory: 4860kb
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: 5ms
memory: 4240kb
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: 4664kb
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: 4292kb
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: 4132kb
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: 4020kb
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: 4240kb
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: 3ms
memory: 4244kb
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'