QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#329968#185. Bridgesjunbin29 1905ms11096kbC++145.0kb2024-02-17 10:05:302024-02-17 10:05:32

Judging History

你现在查看的是最新测评结果

  • [2024-02-17 10:05:32]
  • 评测
  • 测评结果:29
  • 用时:1905ms
  • 内存:11096kb
  • [2024-02-17 10:05:30]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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%