QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#329968 | #185. Bridges | junbin | 29 | 1905ms | 11096kb | C++14 | 5.0kb | 2024-02-17 10:05:30 | 2024-02-17 10:05:32 |
Judging History
answer
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <queue>
#include <list>
#include<fstream>
#include <bitset>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define pb push_back
#define P pair
#define V vector
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define FFOR(i, a, b) for (int i = a; i <= b; ++i)
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
out << "{"; bool first = true;
for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
out << "["; bool first = true;
for (auto v : a) { out << (first ? "" : ", "); out << v; first = 0;}
out << "]";
return out;
}
const int N = 200000 + 10;
int ans[N], L[2010], R[2010], timing[N];
bool vis1[N], vis2[N];
vector<int> T[2010];
struct E {
int u, v, w, t, i;
} e[N], ee[N];
struct Q {
int u, w, t, i;
bool operator< (const Q& other) {
return w > other.w;
}
} q[N];
bool comp1(E& e1, E& e2) {
return e1.t < e2.t;
}
bool comp2(E& e1, E& e2) {
return e1.w > e2.w;
}
//DSU
struct Node {
int fax, fay, w, sz;
} stk[N];
int p[N], rk[N], sz[N];
int top = 0;
int find(int x) {
return p[x] == x ? x : find(p[x]);
}
bool merge(int u, int v) {
int fax = find(u), fay = find(v);
if(rk[fax] > rk[fay]) {
swap(fax, fay);
}
//注意这里,否则树的高度会不一样而导致TLE
if(fax != fay) {
stk[top++] = (Node){fax, fay, rk[fay], sz[fay]};
p[fax] = fay;
sz[fay] += sz[fax];
rk[fay] = max(rk[fax], rk[fay]);
return true;
}
return false;
}
void undo() {
while(top > 0) {
top--;
int fax = stk[top].fax, fay = stk[top].fay;
p[fax] = fax;
rk[fay] = stk[top].w;
sz[fay] = stk[top].sz;
}
}
////////////////////////////////////////////////////////////////////
void init(int n) {
top = 0;
for(int i = 0; i <= n; i++) {
p[i] = i, sz[i] = 1, rk[i] = 0, vis1[i] = false;
}
}
int cnt = 0;
void solve() {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);
e[i].t = 0;
e[i].i = i;
}
int k = 0, ti = 0, o = 0;
scanf("%d", &o);
for(int i = 0; i < o; i++) {
int op;
scanf("%d", &op);
if(op == 1) {
int ith, w;
scanf("%d%d", &ith, &w);
e[m] = {e[ith - 1].u, e[ith - 1].v, w, ++ti, ith - 1};
m++;
} else {
scanf("%d%d", &q[k].u, &q[k].w);
q[k].t = ++ti;
q[k].i = k;
k++;
}
}
for(int i = 0; i < m; i++) {
ee[i] = {e[i].u, e[i].v, e[i].w, e[i].t, e[i].i};
}
sort(e, e + m, comp1); //按w 从大到小排序
sort(q, q + k); //按t 从小到大排序
//分块范围初始化
int s = sqrt(m);
int t = 0;
for(int i = 0; i < m; i += s) {
L[t] = i;
R[t] = min(m - 1, i + s - 1);
t++;
}
//分块分配处理
for(int i = 0; i < k; i++) {
int j = 0;
while(j < t && e[R[j]].t <= q[i].t) j++;
T[min(j, t - 1)].push_back(i);
}
//for(int i = 0; i < t; i++) cout << i << " " << T[i] << endl;
for(int i = 0; i < t; i++) {
int l = L[i], r = R[i];
init(n);
sort(e, e + l, comp2);
for(int o = l; o <= r; o++) {
vis1[e[o].i] = true;
}
vector<E> cur;
int j = 0;
for(int& x : T[i]) {
int u = q[x].u, w = q[x].w, idx = q[x].i;
while(j < l && e[j].w >= w) {
if(e[j].w != ee[e[j].i].w) { //not the newest
} else {
if(vis1[e[j].i]) {
cur.push_back(e[j]);
} else {
merge(e[j].u, e[j].v);
}
}
j++;
}
top = 0;
vector<int> evisit;
for(int o = r; o >= l; o--) {
if(e[o].t <= q[x].t) {
if(!vis2[e[o].i]) {
if(e[o].w >= w) {
merge(e[o].u, e[o].v);
}
}
evisit.push_back(e[o].i);
vis2[e[o].i] = true;
}
}
for(int o = cur.size() - 1; o >= 0; o--) {
if(cur[o].t <= q[x].t) {
if(!vis2[cur[o].i]) {
if(cur[o].w >= w) {
merge(cur[o].u, cur[o].v);
}
}
evisit.push_back(cur[o].i);
vis2[cur[o].i] = true;
}
}
for(int eidx: evisit) {
vis2[eidx] = false;
}
ans[idx] = sz[find(u)];
undo();
}
for(int o = l; o <= r; o++) { //update edge with the newest info
ee[e[o].i].w = e[o].w;
}
}
for(int i = 0; i < k; i++) {
printf("%d\n", ans[i] == 0 ? 1 : ans[i]);
}
}
int main() {
int t = 1;
while(t--) {
solve();
}
return 0;
}
详细
Subtask #1:
score: 13
Accepted
Test #1:
score: 13
Accepted
time: 1ms
memory: 5876kb
input:
3 4 1 2 5 2 3 2 3 1 4 2 3 8 5 2 1 5 1 4 1 2 2 5 1 1 1 2 3 2
output:
3 2 3
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1ms
memory: 3868kb
input:
7 8 1 2 5 1 6 5 2 3 5 2 7 5 3 4 5 4 5 5 5 6 5 6 7 5 12 2 1 6 1 1 1 2 1 2 1 2 3 2 2 2 1 5 2 1 3 1 2 2 4 2 4 2 1 8 1 2 1 1 2 1 3
output:
1 7 7 5 7 7 4
result:
ok 7 lines
Test #3:
score: 0
Accepted
time: 1ms
memory: 3952kb
input:
5 5 5 3 81 2 4 49 4 1 63 4 3 74 1 2 85 10 2 2 22 2 2 20 1 3 49 2 1 77 1 3 44 1 1 6 2 3 49 2 4 31 2 2 54 2 2 7
output:
5 5 2 4 4 2 4
result:
ok 7 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 3840kb
input:
5 10 1 3 51 1 2 74 2 4 63 1 4 86 2 5 9 5 1 28 5 4 1 2 1 23 2 5 16 3 1 75 10 2 2 37 1 6 24 1 1 24 2 5 65 1 7 57 2 1 82 2 1 26 1 4 12 2 2 15 1 4 70
output:
4 1 2 5 5
result:
ok 5 lines
Test #5:
score: 0
Accepted
time: 145ms
memory: 6212kb
input:
100 1000 26 42 977322268 4 29 374382133 1 19 717262653 80 56 835233390 58 54 591443635 63 6 579687470 85 81 118110131 33 100 533388119 24 46 591205239 94 32 637495476 60 93 638216409 55 7 413175730 38 43 414269997 48 30 773236579 67 27 441100383 44 36 784705206 28 56 300064078 13 60 490548719 94 19 ...
output:
100 100 100 100 100 100 100 100 17 100 100 100 100 100 5 100 98 100 100 100 100 100 100 100 100 100 100 100 100 96 100 2 42 100 100 100 86 97 100 100 100 98 100 100 100 100 100 97 100 100 100 100 100 100 100 100 100 100 100 100 100 98 100 100 100 100 100 5 100 100 100 100 100 98 100 100 100 100 1 10...
result:
ok 4938 lines
Test #6:
score: 0
Accepted
time: 3ms
memory: 4092kb
input:
1 0 10000 2 1 198824732 2 1 485321921 2 1 632483476 2 1 51814372 2 1 599796663 2 1 786502474 2 1 231528808 2 1 911511073 2 1 372581312 2 1 168699670 2 1 155928174 2 1 636544973 2 1 221309003 2 1 934838177 2 1 927074369 2 1 66460573 2 1 854380894 2 1 763039163 2 1 203254324 2 1 525763932 2 1 58538356...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 10000 lines
Test #7:
score: 0
Accepted
time: 14ms
memory: 4228kb
input:
14 91 14 9 741787656 13 11 380113631 4 1 156765724 5 10 110432834 3 2 1 5 8 39463185 6 7 725978322 13 4 785136504 8 11 446396092 2 1 949863738 10 9 808326751 3 14 623625192 13 1 73346434 4 3 319943247 10 11 874189144 6 5 177923890 14 11 892698206 10 8 602358072 10 12 7684455 14 8 228264999 12 2 8612...
output:
14 14 14 14 1 2 10 14 14 14 1 14 10 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 14 1 14 14 12 14 1 14 14 14 14 1 14 2 14 14 14 14 14 14 14 14 14 14 13 14 14 14 14 14 14 14 1 14 14 14 2 14 14 14 14 14 14 14 3 14 14 14 14 14 14 14 1 14 14 2 14 14 14 14 14 14 14 14 14 14 14 14 1 14 14 14 14 14 1 14...
result:
ok 5047 lines
Test #8:
score: 0
Accepted
time: 22ms
memory: 4332kb
input:
14 91 14 9 811041661 13 11 347161250 4 1 1000000000 5 10 1000000000 3 2 190616738 5 8 1000000000 6 7 1000000000 13 4 839799889 8 11 1000000000 2 1 1000000000 10 9 925475672 3 14 327778434 13 1 709412306 4 3 696232213 10 11 1000000000 6 5 1000000000 14 11 994412543 10 8 1000000000 10 12 1000000000 14...
output:
10 10 10 10 10 10 14 10 10 14 14 10 10 14 10 14 14 10 10 10 10 10 14 14 13 10 10 10 10 10 14 10 10 10 10 10 10 14 10 10 10 14 10 10 10 10 10 10 10 10 14 10 10 14 10 1 10 13 14 14 14 10 10 10 10 10 10 10 10 10 14 10 10 10 10 14 10 10 10 10 10 10 10 10 10 10 14 10 10 10 10 10 10 14 14 14 10 10 14 14 1...
result:
ok 5085 lines
Test #9:
score: 0
Accepted
time: 16ms
memory: 4580kb
input:
100 100 74 34 685914765 44 9 1 41 36 6 49 22 1 40 84 1 7 40 1 57 31 264482875 16 87 3 66 10 3 68 7 2 92 43 2 33 57 736695588 42 23 2 64 45 1 85 81 4 43 84 1 62 91 2 13 49 2 95 50 1 76 54 1 49 88 1 37 73 2 48 60 1 65 85 3 69 62 2 60 26 1 15 12 1 82 51 2 100 25 3 21 78 1 59 52 1 10 49 2 80 60 2 89 8 3...
output:
84 15 84 84 84 84 84 84 1 84 5 1 84 3 3 1 1 1 1 84 10 84 7 1 84 1 84 1 1 4 84 3 19 1 15 84 84 84 1 84 84 84 84 2 1 84 4 1 2 84 1 84 84 84 2 2 84 84 1 2 84 3 1 5 1 1 4 1 1 84 84 3 20 84 4 6 84 9 4 1 84 1 1 1 84 84 84 84 84 1 84 21 5 2 2 1 1 84 4 84 84 84 5 1 4 6 84 21 1 21 84 84 84 2 84 1 1 1 84 1 84...
result:
ok 4993 lines
Test #10:
score: 0
Accepted
time: 15ms
memory: 4304kb
input:
100 100 74 34 1000000000 44 9 715200993 41 36 904630372 49 22 962500864 40 84 729454076 7 40 377495011 57 31 1000000000 16 87 325040395 66 10 52188391 68 7 212790030 92 43 78499164 33 57 1000000000 42 23 501453286 64 45 269034829 85 81 219465148 43 84 451775169 62 91 579206993 13 49 553447314 95 50 ...
output:
1 60 5 2 24 22 2 1 1 4 40 1 77 72 1 4 1 38 1 2 42 1 3 1 76 1 1 1 2 51 1 28 74 1 38 80 76 1 1 69 3 83 1 5 5 5 83 68 5 2 1 1 1 81 5 2 1 4 1 2 5 52 1 5 78 1 51 2 5 71 2 66 1 84 2 36 1 8 3 1 1 1 78 1 68 81 16 76 2 84 84 2 5 1 63 2 1 63 1 1 74 76 5 1 5 3 1 1 1 1 3 1 1 3 2 5 1 2 24 5 1 1 21 1 1 81 21 4 3 ...
result:
ok 4993 lines
Test #11:
score: 0
Accepted
time: 17ms
memory: 4508kb
input:
100 100 74 34 228801803 44 9 1 41 36 4 49 22 1 40 84 4 7 40 3 57 31 704030998 16 87 4 66 10 1 68 7 7 92 43 1 33 57 728028523 42 23 1 64 45 3 85 81 4 43 84 3 62 91 3 13 49 1 95 50 1 76 54 1 49 88 1 37 73 3 48 60 4 65 85 1 69 62 1 60 26 4 15 12 3 82 51 4 100 25 1 21 78 4 59 52 3 10 49 1 80 60 2 89 8 6...
output:
5 84 84 84 84 84 1 84 84 84 84 84 1 84 84 84 84 1 84 84 1 1 84 1 84 1 84 84 84 84 84 84 84 84 84 84 84 84 84 84 1 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 1 84 84 84 1 84 84 84 1 84 84 84 84 84 84 84 84 84 1 84 84 84 84 5 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84 84...
result:
ok 4976 lines
Test #12:
score: 0
Accepted
time: 13ms
memory: 4212kb
input:
100 100 75 55 18370417 87 15 24759751 35 90 180232308 93 13 4822137 52 63 94962544 47 83 518290304 79 21 1829303 7 97 537385812 75 19 52188390 25 8 212790030 87 43 24037796 44 94 324191076 9 92 333255997 54 51 12968272 34 6 253267674 95 64 20519430 31 58 28891962 12 23 575634244 50 4 110619991 33 9 ...
output:
3 1 82 100 1 2 100 1 1 1 2 22 6 3 10 3 16 10 22 2 1 1 4 1 2 8 3 5 7 1 32 1 6 12 8 2 6 3 6 3 1 55 100 1 4 2 5 4 1 1 2 13 75 3 1 55 6 2 3 1 9 1 13 1 9 60 3 1 1 100 1 1 1 100 15 1 3 3 75 6 100 12 15 1 2 3 8 1 8 15 6 1 3 1 1 14 4 1 1 3 8 2 1 12 24 4 2 1 30 3 100 1 1 1 4 24 1 6 1 1 15 4 30 1 13 1 3 1 3 7...
result:
ok 4993 lines
Test #13:
score: 0
Accepted
time: 12ms
memory: 4228kb
input:
100 100 75 55 827381885 87 15 189426033 35 90 314088225 93 13 962500864 52 63 771307313 47 83 930460632 79 21 691878465 7 97 859582759 75 19 557403081 25 8 989321957 87 43 217067250 44 94 805985038 9 92 924454229 54 51 269034829 34 6 811380927 95 64 180328209 31 58 436656654 12 23 947277637 50 4 917...
output:
5 8 1 7 1 7 6 48 11 3 1 13 2 5 1 60 1 1 13 1 2 45 2 1 2 1 5 13 1 4 3 1 4 52 52 4 31 1 52 4 1 1 2 1 2 1 2 1 3 24 60 2 8 1 14 2 1 2 3 2 7 1 8 4 8 2 100 2 4 19 2 1 8 100 1 4 2 90 17 1 2 48 2 48 1 3 4 3 17 1 3 2 2 2 3 1 4 2 1 1 1 3 1 44 3 5 1 90 1 16 5 14 1 3 2 1 5 63 3 5 1 3 1 42 2 14 5 1 1 1 2 1 4 1 3...
result:
ok 4993 lines
Test #14:
score: 0
Accepted
time: 14ms
memory: 4296kb
input:
100 100 75 55 523280580 87 15 97273903 35 90 24566276 93 13 66762694 52 63 62457076 47 83 14559451 79 21 198058038 7 97 303933384 75 19 357282957 25 8 15676722 87 43 20498361 44 94 361533141 9 92 479521475 54 51 188367392 34 6 351945785 95 64 31785315 31 58 12985500 12 23 63507527 50 4 25758008 33 9...
output:
1 1 5 13 9 1 11 4 7 25 2 13 15 1 13 66 33 3 13 5 1 2 1 1 4 11 13 9 4 1 3 9 16 7 11 1 7 11 28 5 11 13 9 9 13 2 5 10 9 15 4 24 3 3 9 62 15 3 9 1 14 17 1 13 1 17 9 4 1 1 15 11 2 9 9 1 10 4 1 3 9 2 13 1 4 9 9 5 65 1 62 13 13 11 11 1 6 1 1 1 6 8 99 7 3 1 3 1 5 32 1 1 9 3 18 6 4 65 10 66 1 9 3 2 4 10 4 65...
result:
ok 4952 lines
Test #15:
score: 0
Accepted
time: 18ms
memory: 4500kb
input:
100 150 72 39 459437566 99 33 240975967 60 42 71297038 100 66 81817608 7 97 40586687 94 44 488433191 9 33 155257410 38 59 258106533 34 6 7722722 97 89 212790030 73 34 78499164 83 88 261128013 39 98 335913783 20 81 140652810 14 30 129337570 83 47 56555466 18 2 676617230 37 42 79132016 80 35 633142513...
output:
1 1 11 1 1 3 6 41 4 1 25 2 5 5 2 46 45 2 23 34 34 26 11 26 1 6 23 1 100 5 100 2 1 5 30 6 4 61 62 26 5 26 100 26 100 2 1 5 3 1 66 27 26 26 100 3 26 16 24 26 26 18 1 7 1 3 34 67 1 7 5 30 100 4 3 18 27 18 1 3 3 71 19 66 7 24 39 9 26 98 39 100 1 42 38 5 11 100 42 26 1 37 1 27 100 40 42 37 5 37 37 58 40 ...
result:
ok 5046 lines
Test #16:
score: 0
Accepted
time: 17ms
memory: 4248kb
input:
100 150 72 39 950686765 99 33 716054509 60 42 836724016 100 66 497108440 7 97 168321467 94 44 992895576 9 33 938438676 38 59 548639568 34 6 773535187 97 89 982737825 73 34 894334764 83 88 687830748 39 98 950242721 20 81 613284326 14 30 602412784 83 47 673179224 18 2 917339878 37 42 581986238 80 35 9...
output:
1 4 3 3 22 1 2 22 2 3 1 4 20 1 1 58 22 30 3 1 2 1 8 1 16 4 3 22 1 46 2 2 16 3 1 1 14 5 1 1 8 2 1 1 100 5 16 1 1 6 3 1 1 1 100 4 100 14 27 45 1 2 1 10 1 4 31 100 1 3 1 1 2 1 1 1 17 2 50 24 2 1 40 54 1 2 2 4 4 1 1 1 4 31 1 1 1 1 4 100 8 11 7 22 2 2 16 1 4 1 2 1 4 1 13 5 18 1 99 1 10 25 100 1 10 3 18 9...
result:
ok 5046 lines
Test #17:
score: 0
Accepted
time: 17ms
memory: 4260kb
input:
100 150 72 39 23280580 99 33 97273903 60 42 24566276 100 66 254262694 7 97 437457076 94 44 139559451 9 33 10558038 38 59 241433384 34 6 107282957 97 89 140676722 73 34 20498361 83 88 111533141 39 98 604521475 20 81 188367392 14 30 226945785 83 47 94285315 18 2 512985500 37 42 313507527 80 35 1507580...
output:
61 1 22 3 18 14 19 1 19 5 1 1 37 1 100 30 72 18 98 99 1 1 1 100 3 30 17 23 18 1 18 18 1 100 2 8 2 30 18 8 29 1 1 45 100 1 28 1 24 6 1 1 100 1 2 15 1 69 9 30 1 17 29 69 1 99 20 11 99 99 6 1 6 29 1 23 99 11 1 29 9 3 3 1 18 22 22 42 4 28 29 1 2 1 98 3 29 1 1 29 18 99 1 19 1 41 29 8 97 1 16 8 68 3 8 8 1...
result:
ok 5078 lines
Test #18:
score: 0
Accepted
time: 17ms
memory: 4568kb
input:
100 100 92 90 2 13 45 2 64 25 1 56 84 1 65 57 1 95 8 1 69 40 2 19 62 1 93 82 1 69 86 1 13 95 2 32 36 1 30 69 2 28 85 2 61 19 2 16 95 1 18 75 2 99 24 2 75 54 2 94 17 1 5 4 1 77 43 2 46 97 2 20 2 1 61 53 2 92 73 1 27 43 1 10 41 1 39 13 2 58 37 1 57 70 1 4 18 1 14 69 1 75 52 2 38 50 1 50 97 1 81 10 2 1...
output:
10 2 1 80 2 80 3 1 3 80 80 80 80 3 2 1 80 1 80 80 1 4 80 80 12 80 12 80 1 80 3 12 12 80 80 80 1 2 80 80 4 1 80 1 1 1 2 80 1 80 2 1 1 1 17 1 1 80 80 3 1 80 1 80 80 80 1 1 5 80 11 2 80 80 80 1 2 80 1 1 2 4 80 1 2 11 4 80 18 80 18 1 4 80 1 2 80 80 1 80 80 6 80 1 1 6 7 2 6 16 80 4 80 1 2 1 2 80 1 80 16 ...
result:
ok 4949 lines
Test #19:
score: 0
Accepted
time: 10ms
memory: 4252kb
input:
100 100 20 34 3 91 98 2 40 13 1 34 24 1 55 90 3 12 23 1 87 80 3 96 71 1 50 98 2 26 3 1 32 66 1 64 45 3 60 44 3 42 77 3 54 78 2 99 2 2 36 46 1 51 10 2 67 96 2 15 60 1 8 25 3 51 78 1 19 20 3 54 59 3 72 68 1 22 29 1 80 51 2 54 68 1 70 77 1 9 91 2 41 64 2 17 22 3 5 91 2 58 39 1 66 15 2 8 6 3 66 80 3 71 ...
output:
10 1 5 81 81 4 52 1 81 1 1 1 81 2 1 50 1 57 1 2 1 2 81 1 5 1 16 16 3 1 1 1 2 2 81 81 3 1 81 2 1 2 81 4 1 81 3 1 1 81 81 30 2 81 30 81 1 81 30 1 1 81 81 3 2 1 32 4 1 1 1 1 81 81 3 1 4 2 1 81 1 48 6 4 1 81 81 1 81 1 4 81 1 81 6 1 1 3 81 1 52 81 1 52 81 5 81 81 1 81 6 5 2 81 1 2 1 9 4 1 1 81 1 1 4 40 1...
result:
ok 5065 lines
Subtask #2:
score: 16
Accepted
Test #20:
score: 16
Accepted
time: 1256ms
memory: 9872kb
input:
50000 49999 1 2 976392398 2 3 773336157 3 4 849545817 4 5 194340376 5 6 386778507 6 7 40561907 7 8 260116638 8 9 85673124 9 10 149683208 10 11 724746156 11 12 155084527 12 13 416939763 13 14 753621724 14 15 384948880 15 16 625917615 16 17 833747431 17 18 764302034 18 19 4518648 19 20 405679793 20 21...
output:
7 2 24 1 3 8 1 2 6 2 535 4 3 2 7 13 40 110 3 41 6 1 108 491 28 1 1 4 2 11 5 9 2 1 2 1 9 1 1 3 1 14 3 1 1 10 44 3 2 3 3 1 1 18 3 2 2 2 1 9 1 15 17 7 1 1 1 4 1 2 6 3 1 1 5 1 10 1 5 2 1 14 14 3 28 17 1 6 1 3 1 9 3 10 2 32 54 4 1 2 2 18 1 1 5 1 11 2 10 1 2 5 4 1 1 2 3 4 1 1 128 17 3 1 2 2 1 160 1 1 2 3 ...
result:
ok 49863 lines
Test #21:
score: 0
Accepted
time: 1238ms
memory: 9864kb
input:
50000 49999 1 2 491 2 3 15360 3 4 24312 4 5 17754 5 6 40601 6 7 30620 7 8 69533 8 9 144923 9 10 304551 10 11 264913 11 12 265173 12 13 135700 13 14 61571 14 15 6841 15 16 413217 16 17 596083 17 18 157633 18 19 68400 19 20 348725 20 21 494086 21 22 327898 22 23 569190 23 24 195301 24 25 402492 25 26 ...
output:
6 7 16 2 13 24 24 8 1 3 5 257 1 3 6 1 112 2 5 2 11 1 6 2 6 1 1 4 177 7 19 1 1 42 10 2 25 4 24 4 1 3 3 2 1 1 5 1 3 2 13 1 1 1 2 3 5 3 9 2 16 4 10 6 7 3 1 2 17 37 3 1 4 1 4 1 3 7 1 2 2 1 135 3 34 5 2 2 8 2 1 1 1 1 4 3 1 3 2 5 2 1 5 1 2 5 503 3 1 9 7 1 2 4 2 3 5 9 2 15 3 7 9 16 1 28 5 2 5 4 2 3 8 9 4 1...
result:
ok 49979 lines
Test #22:
score: 0
Accepted
time: 1274ms
memory: 9872kb
input:
50000 49999 1 2 20928 2 3 33937 3 4 35582 4 5 123172 5 6 100214 6 7 105156 7 8 46684 8 9 124995 9 10 13728 10 11 209960 11 12 206098 12 13 146953 13 14 370445 14 15 141005 15 16 536276 16 17 80350 17 18 258276 18 19 401626 19 20 32874 20 21 125207 21 22 357075 22 23 598244 23 24 46414 24 25 609917 2...
output:
3 1 1 1 2 1 2 10 7 1 43 3 6 1 4 1 8 1 82 5 3 1 1 2 1 11 5 45 21 1 1 10 2 5 8 2 1 12 1 29 2 1 4 5 2 56 3 3 3 14 1 1 29 9 160 4 3 5 2 2 1 2 6 3 2 11 2 8 1 8 3 3 9 199 1 1 1 1 1 1 1 11 23 2 2 9 339 2 2 1 2 3 1 1 116 6 5 5 10 3 1 1 2 1 18 1 1 6 1 1 8 3 3 1 1 24 1 1 3 1 1 5 12 10 1 6 1 3 2 4 1 2 1 5 6 1 ...
result:
ok 50005 lines
Test #23:
score: 0
Accepted
time: 1326ms
memory: 9936kb
input:
50000 49999 1 2 111167988 2 3 402479521 3 4 873342766 4 5 303335487 5 6 357259867 6 7 944570848 7 8 227864068 8 9 137899415 9 10 782881158 10 11 545137901 11 12 125756079 12 13 713912399 13 14 516355545 14 15 306731193 15 16 244028251 16 17 175980262 17 18 956260270 18 19 92690286 19 20 344996907 20...
output:
1 8 1 1 1 1 6 11 21 12 5 3 105 1 1 2 4 5 1 16 1 2 1 3 1 3 2 1 1 2 1 30 2 29 9 8 6 16 1 24 5 8 2 1 5 33 10 12 5 28 10 2 1 1 6 1 2 1 1 1 1 17 7 12 2 3 10 6 2 89 38 2 2 1 2 5 6 1 1 107 47 1 1 1 1 9 1 1 13 2 12 6 1 1 9 9 2 16 1 2 2 2 15 1 4 5 5 1 1 116 5 1 7 5 3 18 1 1 1 14 1 2 1 1 1 3185 1 3 3 2 1 3 7 ...
result:
ok 49979 lines
Test #24:
score: 0
Accepted
time: 1313ms
memory: 10160kb
input:
50000 49999 1 2 993457878 2 3 126364173 3 4 200415238 4 5 739704607 5 6 676532686 6 7 557507714 7 8 71727068 8 9 337809709 9 10 681106495 10 11 599345798 11 12 346312387 12 13 39200895 13 14 943426213 14 15 506779546 15 16 379338416 16 17 14615880 17 18 816406736 18 19 211045210 19 20 838922528 20 2...
output:
5 9 18 53 19 1 25 4 19 1 1 1 1 1 11 1 1 2 1 9 1 13 16 5 1 2 1 1 1 7 1 1 16 1 1 5 3 2 3 3 11 2 1 1 12 1 16987 4 12 1 1 1 5 5 5 1 1 4 1 4 2 1 3 1 4 1 1 2 5 2 18 1 3 200 1 4 2 7 1 1 1 2 44 2 1 10 11 2 3 12 1 3 4 10 4 7 1 16 6 1 13 4 1 5 3 2 1 2 2 2 1 31 40 3 2 1 3 1 86 2 2 1 1 1 1 15 2 1 1 1 6 1 1 7 1 ...
result:
ok 50005 lines
Test #25:
score: 0
Accepted
time: 1455ms
memory: 10660kb
input:
50000 49999 1 2 2180 2 3 39922 3 4 2857 4 5 41405 5 6 71574 6 7 34628 7 8 271216 8 9 134571 9 10 77206 10 11 98084 11 12 86039 12 13 449514 13 14 490107 14 15 450572 15 16 139688 16 17 639236 17 18 247981 18 19 75121 19 20 300881 20 21 7682 21 22 248842 22 23 599408 23 24 647942 24 25 7276 25 26 470...
output:
49496 49499 49314 30098 32346 32346 49499 30098 42345 4779 49496 42345 49314 32346 49496 49314 30098 1640 30098 30098 30098 6969 6968 40954 49314 30098 2248 30098 30098 403 40954 6969 49314 6969 30098 49498 30098 4779 40954 49499 6968 42345 30098 32346 1345 32346 49314 32346 40954 32346 6969 6969 33...
result:
ok 49911 lines
Test #26:
score: 0
Accepted
time: 1457ms
memory: 10616kb
input:
49999 49998 1 2 2541 2 3 57948 3 4 37666 4 5 66268 5 6 42284 6 7 115405 7 8 248366 8 9 262167 9 10 145846 10 11 47627 11 12 431021 12 13 218051 13 14 401077 14 15 549059 15 16 169347 16 17 363982 17 18 490171 18 19 370535 19 20 480055 20 21 327730 21 22 278018 22 23 231965 23 24 256156 24 25 329573 ...
output:
450 33828 47494 47494 1249 47493 9064 9064 24764 8175 47493 8175 33828 19203 19203 3968 1811 8175 5561 1689 42003 8175 33828 42003 33828 47494 19203 5561 24764 47494 3968 16782 24764 19203 24764 47494 24764 8175 24764 47493 9064 75 9064 1689 47494 1689 1689 24764 5561 2976 33828 3968 33828 78 24764 ...
result:
ok 50105 lines
Test #27:
score: 0
Accepted
time: 1429ms
memory: 10880kb
input:
49999 49998 1 2 23701 2 3 57539 3 4 70283 4 5 136271 5 6 141212 6 7 184696 7 8 228429 8 9 29895 9 10 31218 10 11 282781 11 12 29995 12 13 131524 13 14 133988 14 15 197273 15 16 351724 16 17 391575 17 18 253620 18 19 611546 19 20 216997 20 21 305541 21 22 118275 22 23 306021 23 24 482979 24 25 709132...
output:
26373 8528 1944 10472 1430 6356 3806 5934 1944 49998 8528 11437 369 363 36932 4327 3351 3351 3806 6496 1944 49973 5934 13041 19188 1857 652 2143 13254 13254 12975 49998 599 8528 1944 10472 5934 8528 19 10472 13254 10472 1935 4327 6356 11339 36932 13254 10472 4257 3806 610 6496 5934 2220 11437 1300 4...
result:
ok 50026 lines
Test #28:
score: 0
Accepted
time: 25ms
memory: 5924kb
input:
1 0 100000 2 1 710454586 2 1 30174257 2 1 685675008 2 1 417816804 2 1 327755609 2 1 841371333 2 1 301370841 2 1 143821498 2 1 232099091 2 1 977178764 2 1 572665966 2 1 913418066 2 1 808399404 2 1 22331931 2 1 434460344 2 1 40437984 2 1 997406768 2 1 40071081 2 1 268638772 2 1 541398526 2 1 983507437...
output:
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 100000 lines
Test #29:
score: 0
Accepted
time: 674ms
memory: 10500kb
input:
50000 49999 1 2 2 2 3 2 3 4 1 4 5 2 5 6 2 6 7 1 7 8 1 8 9 2 9 10 2 10 11 1 11 12 1 12 13 2 13 14 1 14 15 1 15 16 1 16 17 1 17 18 1 18 19 2 19 20 2 20 21 1 21 22 2 22 23 1 23 24 1 24 25 1 25 26 1 26 27 1 27 28 2 28 29 2 29 30 2 30 31 2 31 32 1 32 33 1 33 34 2 34 35 2 35 36 2 36 37 2 37 38 2 38 39 1 3...
output:
50000 50000 50000 50000 6 2 2 50000 50000 50000 50000 50000 50000 6 50000 1 1 50000 50000 4 4 50000 1 50000 50000 3 50000 2 50000 2 3 50000 1 50000 4 50000 50000 4 50000 50000 5 50000 9 50000 50000 10 3 5 50000 1 50000 50000 50000 50000 1 50000 50000 50000 3 50000 2 3 1 50000 50000 50000 50000 3 500...
result:
ok 49970 lines
Test #30:
score: 0
Accepted
time: 652ms
memory: 10048kb
input:
50000 49999 1 2 2 2 3 2 3 4 2 4 5 2 5 6 1 6 7 3 7 8 1 8 9 3 9 10 3 10 11 1 11 12 3 12 13 2 13 14 2 14 15 2 15 16 3 16 17 3 17 18 3 18 19 1 19 20 2 20 21 3 21 22 1 22 23 2 23 24 1 24 25 3 25 26 3 26 27 3 27 28 3 28 29 3 29 30 3 30 31 1 31 32 3 32 33 1 33 34 2 34 35 2 35 36 2 36 37 1 37 38 3 38 39 1 3...
output:
50000 1 1 50000 50000 1 50000 50000 1 3 1 2 6 50000 50000 50000 50000 2 2 4 2 50000 5 3 50000 8 1 1 3 2 50000 50000 2 9 1 50000 50000 5 50000 1 7 50000 50000 6 1 9 5 4 4 1 3 50000 1 50000 3 2 2 50000 2 50000 4 5 50000 1 4 50000 5 50000 7 3 3 6 2 50000 3 12 50000 2 2 50000 9 50000 5 50000 50000 50000...
result:
ok 50021 lines
Test #31:
score: 0
Accepted
time: 955ms
memory: 9680kb
input:
49999 49998 1 2 17203 2 3 2847 3 4 78198 4 5 153265 5 6 167348 6 7 223540 7 8 247201 8 9 165110 9 10 39406 10 11 169131 11 12 77633 12 13 189498 13 14 426647 14 15 370032 15 16 150693 16 17 137818 17 18 532098 18 19 516136 19 20 378632 20 21 155025 21 22 514837 22 23 297354 23 24 420776 24 25 391135...
output:
16669 3311 16669 16669 27851 626 13228 12829 2938 43909 399 2604 27851 10120 442 16669 13228 3783 3311 12829 16669 4348 27851 673 3311 624 12829 208 4348 4398 16669 2830 16669 16669 16669 16669 16669 10120 16669 1063 1424 13228 16669 16669 624 1424 2604 16669 16669 12829 12829 10120 12829 21017 2107...
result:
ok 89927 lines
Test #32:
score: 0
Accepted
time: 1905ms
memory: 11096kb
input:
49999 49998 1 2 15625 2 3 58909 3 4 79176 4 5 78230 5 6 108291 6 7 91661 7 8 34888 8 9 86333 9 10 196105 10 11 339006 11 12 66021 12 13 415608 13 14 107020 14 15 197675 15 16 190986 16 17 61241 17 18 430747 18 19 10073 19 20 696099 20 21 681217 21 22 687623 22 23 216763 23 24 8263 24 25 341165 25 26...
output:
208 53 4539 359 704 2952 7275 15294 1317 8926 49868 9467 10243 49868 9467 8926 4254 1224 2952 1463 4254 9467 10243 4539 9467 7275 29898 10243 9467 11529 2253 9467 7275 29898 9467 29898 9467 7275 4254 9467 40141 1127 45624 47145 519 1288 4254 40141 2952 49999 7275 29898 2952 10243 7275 40141 640 6918...
result:
ok 9962 lines
Subtask #3:
score: 0
Time Limit Exceeded
Test #33:
score: 0
Time Limit Exceeded
input:
32767 32766 1 2 152523690 1 3 736211233 2 4 163158345 2 5 200010458 3 6 902682843 3 7 427399287 4 8 770411775 4 9 322256303 5 10 252775416 5 11 346597970 6 12 297314023 6 13 727299741 7 14 985621564 7 15 101953231 8 16 405434218 8 17 421655547 9 18 817411034 9 19 310455840 10 20 355126049 10 21 7038...
output:
result:
Subtask #4:
score: 0
Time Limit Exceeded
Test #45:
score: 0
Time Limit Exceeded
input:
50000 100000 35231 1616 822934828 1668 2202 768458723 26049 41810 238904165 15936 42751 466996423 41068 21425 588205829 29502 11760 732391267 13029 44741 930695124 46168 22085 155239713 9505 43779 638894800 18665 43842 298794735 41763 15511 727702105 7865 27776 53447691 32904 34081 844499614 26327 9...
output:
result:
Subtask #5:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #3:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
100%
Accepted
Dependency #3:
0%