QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#298336#7898. I Just Want... One More...ucup-team1134#AC ✓264ms46316kbC++2311.9kb2024-01-06 00:20:112024-01-06 00:20:11

Judging History

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

  • [2024-01-06 00:20:11]
  • 评测
  • 测评结果:AC
  • 用时:264ms
  • 内存:46316kb
  • [2024-01-06 00:20:11]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=1000005;
const ll INF=1LL<<60;

// https://hitonanode.github.io/cplib-cpp/graph/dulmage_mendelsohn_decomposition.hpp.html

#pragma once
#include <cassert>
#include <iostream>
#include <vector>

// Bipartite matching of undirected bipartite graph (Hopcroft-Karp)
// https://ei1333.github.io/luzhiled/snippets/graph/hopcroft-karp.html
// Comprexity: O((V + E)sqrtV)
// int solve(): enumerate maximum number of matching / return -1 (if graph is not bipartite)
struct BipartiteMatching {
    int V;
    std::vector<std::vector<int>> to; // Adjacency list
    std::vector<int> dist;            // dist[i] = (Distance from i'th node)
    std::vector<int> match;           // match[i] = (Partner of i'th node) or -1 (No parter)
    std::vector<int> used, vv;
    std::vector<int> color; // color of each node(checking bipartition): 0/1/-1(not determined)

    BipartiteMatching() = default;
    BipartiteMatching(int V_) : V(V_), to(V_), match(V_, -1), used(V_), color(V_, -1) {}

    void add_edge(int u, int v) {
        assert(u >= 0 and u < V and v >= 0 and v < V and u != v);
        to[u].push_back(v);
        to[v].push_back(u);
    }

    void _bfs() {
        dist.assign(V, -1);
        std::vector<int> q;
        int lq = 0;
        for (int i = 0; i < V; i++) {
            if (!color[i] and !used[i]) q.push_back(i), dist[i] = 0;
        }

        while (lq < int(q.size())) {
            int now = q[lq++];
            for (auto nxt : to[now]) {
                int c = match[nxt];
                if (c >= 0 and dist[c] == -1) q.push_back(c), dist[c] = dist[now] + 1;
            }
        }
    }

    bool _dfs(int now) {
        vv[now] = true;
        for (auto nxt : to[now]) {
            int c = match[nxt];
            if (c < 0 or (!vv[c] and dist[c] == dist[now] + 1 and _dfs(c))) {
                match[nxt] = now, match[now] = nxt;
                used[now] = true;
                return true;
            }
        }
        return false;
    }

    bool _color_bfs(int root) {
        color[root] = 0;
        std::vector<int> q{root};
        int lq = 0;
        while (lq < int(q.size())) {
            int now = q[lq++], c = color[now];
            for (auto nxt : to[now]) {
                if (color[nxt] == -1) {
                    color[nxt] = !c, q.push_back(nxt);
                } else if (color[nxt] == c) {
                    return false;
                }
            }
        }
        return true;
    }

    int solve() {
        for (int i = 0; i < V; i++) {
            if (color[i] == -1 and !_color_bfs(i)) return -1;
        }
        int ret = 0;
        while (true) {
            _bfs();
            vv.assign(V, false);
            int flow = 0;
            for (int i = 0; i < V; i++) {
                if (!color[i] and !used[i] and _dfs(i)) flow++;
            }
            if (!flow) break;
            ret += flow;
        }
        return ret;
    }

    template <class OStream> friend OStream &operator<<(OStream &os, const BipartiteMatching &bm) {
        os << "{N=" << bm.V << ':';
        for (int i = 0; i < bm.V; i++) {
            if (bm.match[i] > i) os << '(' << i << '-' << bm.match[i] << "),";
        }
        return os << '}';
    }
};

#pragma once
#include <algorithm>
#include <cassert>
#include <vector>

// CUT begin
// Directed graph library to find strongly connected components (強連結成分分解)
// 0-indexed directed graph
// Complexity: O(V + E)
struct DirectedGraphSCC {
    int V; // # of Vertices
    std::vector<std::vector<int>> to, from;
    std::vector<int> used; // Only true/false
    std::vector<int> vs;
    std::vector<int> cmp;
    int scc_num = -1;

    DirectedGraphSCC(int V = 0) : V(V), to(V), from(V), cmp(V) {}

    void _dfs(int v) {
        used[v] = true;
        for (auto t : to[v])
            if (!used[t]) _dfs(t);
        vs.push_back(v);
    }
    void _rdfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for (auto t : from[v])
            if (!used[t]) _rdfs(t, k);
    }

    void add_edge(int from_, int to_) {
        assert(from_ >= 0 and from_ < V and to_ >= 0 and to_ < V);
        to[from_].push_back(to_);
        from[to_].push_back(from_);
    }

    // Detect strongly connected components and return # of them.
    // Also, assign each vertex `v` the scc id `cmp[v]` (0-indexed)
    int FindStronglyConnectedComponents() {
        used.assign(V, false);
        vs.clear();
        for (int v = 0; v < V; v++)
            if (!used[v]) _dfs(v);
        used.assign(V, false);
        scc_num = 0;
        for (int i = (int)vs.size() - 1; i >= 0; i--)
            if (!used[vs[i]]) _rdfs(vs[i], scc_num++);
        return scc_num;
    }

    // Find and output the vertices that form a closed cycle.
    // output: {v_1, ..., v_C}, where C is the length of cycle,
    //         {} if there's NO cycle (graph is DAG)
    int _c, _init;
    std::vector<int> _ret_cycle;
    bool _dfs_detectcycle(int now, bool b0) {
        if (now == _init and b0) return true;
        for (auto nxt : to[now])
            if (cmp[nxt] == _c and !used[nxt]) {
                _ret_cycle.emplace_back(nxt), used[nxt] = 1;
                if (_dfs_detectcycle(nxt, true)) return true;
                _ret_cycle.pop_back();
            }
        return false;
    }
    std::vector<int> DetectCycle() {
        int ns = FindStronglyConnectedComponents();
        if (ns == V) return {};
        std::vector<int> cnt(ns);
        for (auto x : cmp) cnt[x]++;
        _c = std::find_if(cnt.begin(), cnt.end(), [](int x) { return x > 1; }) - cnt.begin();
        _init = std::find(cmp.begin(), cmp.end(), _c) - cmp.begin();
        used.assign(V, false);
        _ret_cycle.clear();
        _dfs_detectcycle(_init, false);
        return _ret_cycle;
    }

    // After calling `FindStronglyConnectedComponents()`, generate a new graph by uniting all
    // vertices belonging to the same component(The resultant graph is DAG).
    DirectedGraphSCC GenerateTopologicalGraph() {
        DirectedGraphSCC newgraph(scc_num);
        for (int s = 0; s < V; s++)
            for (auto t : to[s]) {
                if (cmp[s] != cmp[t]) newgraph.add_edge(cmp[s], cmp[t]);
            }
        return newgraph;
    }
};

// 2-SAT solver: Find a solution for  `(Ai v Aj) ^ (Ak v Al) ^ ... = true`
// - `nb_sat_vars`: Number of variables
// - Considering a graph with `2 * nb_sat_vars` vertices
// - Vertices [0, nb_sat_vars) means `Ai`
// - vertices [nb_sat_vars, 2 * nb_sat_vars) means `not Ai`
struct SATSolver : DirectedGraphSCC {
    int nb_sat_vars;
    std::vector<int> solution;
    SATSolver(int nb_variables = 0)
        : DirectedGraphSCC(nb_variables * 2), nb_sat_vars(nb_variables), solution(nb_sat_vars) {}
    void add_x_or_y_constraint(bool is_x_true, int x, bool is_y_true, int y) {
        assert(x >= 0 and x < nb_sat_vars);
        assert(y >= 0 and y < nb_sat_vars);
        if (!is_x_true) x += nb_sat_vars;
        if (!is_y_true) y += nb_sat_vars;
        add_edge((x + nb_sat_vars) % (nb_sat_vars * 2), y);
        add_edge((y + nb_sat_vars) % (nb_sat_vars * 2), x);
    }
    // Solve the 2-SAT problem. If no solution exists, return `false`.
    // Otherwise, dump one solution to `solution` and return `true`.
    bool run() {
        FindStronglyConnectedComponents();
        for (int i = 0; i < nb_sat_vars; i++) {
            if (cmp[i] == cmp[i + nb_sat_vars]) return false;
            solution[i] = cmp[i] > cmp[i + nb_sat_vars];
        }
        return true;
    }
};

#pragma once
//#include "bipartite_matching.hpp"
//#include "strongly_connected_components.hpp"
#include <cassert>
#include <utility>
#include <vector>

// Dulmage–Mendelsohn (DM) decomposition (DM 分解)
// return: [(W+0, W-0), (W+1,W-1),...,(W+(k+1), W-(k+1))]
//         : sequence of pair (left vetrices, right vertices)
//         - |W+0| < |W-0| or both empty
//         - |W+i| = |W-i| (i = 1, ..., k)
//         - |W+(k+1)| > |W-(k+1)| or both empty
//         - W is topologically sorted
// Example:
// (2, 2, [(0,0), (0,1), (1,0)]) => [([],[]),([0,],[1,]),([1,],[0,]),([],[]),]
// Complexity: O(N + (N + M) sqrt(N))
// Verified: https://yukicoder.me/problems/no/1615
std::vector<std::pair<std::vector<int>, std::vector<int>>>
dulmage_mendelsohn(int L, int R, const std::vector<std::pair<int, int>> &edges) {
    for (auto p : edges) {
        assert(0 <= p.first and p.first < L);
        assert(0 <= p.second and p.second < R);
    }

    BipartiteMatching bm(L + R);
    for (auto p : edges) bm.add_edge(p.first, L + p.second);
    bm.solve();

    DirectedGraphSCC scc(L + R);
    for (auto p : edges) scc.add_edge(p.first, L + p.second);
    for (int l = 0; l < L; ++l) {
        if (bm.match[l] >= L) scc.add_edge(bm.match[l], l);
    }

    int nscc = scc.FindStronglyConnectedComponents();
    std::vector<int> cmp_map(nscc, -2);

    std::vector<int> vis(L + R);
    std::vector<int> st;
    for (int c = 0; c < 2; ++c) {
        std::vector<std::vector<int>> to(L + R);
        auto color = [&L](int x) { return x >= L; };
        for (auto p : edges) {
            int u = p.first, v = L + p.second;
            if (color(u) != c) std::swap(u, v);
            to[u].push_back(v);
            if (bm.match[u] == v) to[v].push_back(u);
        }
        for (int i = 0; i < L + R; ++i) {
            if (bm.match[i] >= 0 or color(i) != c or vis[i]) continue;
            vis[i] = 1, st = {i};
            while (!st.empty()) {
                int now = st.back();
                cmp_map[scc.cmp[now]] = c - 1;
                st.pop_back();
                for (int nxt : to[now]) {
                    if (!vis[nxt]) vis[nxt] = 1, st.push_back(nxt);
                }
            }
        }
    }

    int nset = 1;
    for (int n = 0; n < nscc; ++n) {
        if (cmp_map[n] == -2) cmp_map[n] = nset++;
    }
    for (auto &x : cmp_map) {
        if (x == -1) x = nset;
    }
    nset++;

    std::vector<std::pair<std::vector<int>, std::vector<int>>> groups(nset);

    for (int l = 0; l < L; ++l) {
        if (bm.match[l] < 0) continue;
        int c = cmp_map[scc.cmp[l]];
        groups[c].first.push_back(l);
        groups[c].second.push_back(bm.match[l] - L);
    }
    for (int l = 0; l < L; ++l) {
        if (bm.match[l] >= 0) continue;
        int c = cmp_map[scc.cmp[l]];
        groups[c].first.push_back(l);
    }
    for (int r = 0; r < R; ++r) {
        if (bm.match[L + r] >= 0) continue;
        int c = cmp_map[scc.cmp[L + r]];
        groups[c].second.push_back(r);
    }

    return groups;
}

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int Q;cin>>Q;
    while(Q--){
        int N,M;cin>>N>>M;
        vector<pair<int,int>> E;
        for(int i=0;i<M;i++){
            int a,b;cin>>a>>b;
            a--;b--;
            E.push_back(mp(a,b));
        }
        
        sort(all(E));
        E.erase(unique(all(E)),E.end());
        
        vector<pair<vector<int>, vector<int>>> ret = dulmage_mendelsohn(N,N,E);
        
        set<int> A,B;
        for(int x:ret.back().fi) A.insert(x);
        for(int x:ret[0].se) B.insert(x);
        
        ll ans=(ll)(si(ret.back().fi))*(ll)(si(ret[0].se));
        
        for(auto [a,b]:E){
            if(A.count(a)&&B.count(b)) ans--;
        }
        
        cout<<ans<<"\n";
    }
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3624kb

input:

3
4 3
1 2
3 2
4 3
3 3
1 3
2 2
3 1
3 2
1 2
1 2

output:

6
0
4

result:

ok 3 number(s): "6 0 4"

Test #2:

score: 0
Accepted
time: 27ms
memory: 3608kb

input:

10000
5 4
2 2
3 1
5 3
1 1
1 1
1 1
1 1
1 1
2 2
2 2
1 2
1 1
1 1
1 1
1 1
1 1
1 1
2 3
2 1
1 2
1 1
5 5
1 4
2 2
3 1
1 3
1 2
2 4
2 2
2 1
1 2
1 1
5 1
5 3
3 1
2 2
1 1
1 1
3 2
3 1
2 1
5 2
1 2
2 3
5 3
1 5
4 2
1 2
4 1
1 1
2 3
1 1
2 2
2 1
4 1
1 4
3 1
1 1
1 1
1 1
2 1
2 2
3 3
1 3
2 3
2 2
3 3
1 3
3 3
1 2
3 3
2 2
1 ...

output:

6
0
0
2
0
0
0
0
6
0
16
4
0
6
9
9
9
0
9
4
0
1
1
1
0
4
16
12
3
2
16
0
2
2
20
1
0
0
0
0
16
4
4
16
4
9
0
9
0
2
3
0
9
4
9
16
20
0
0
1
12
0
1
2
0
0
1
0
0
2
2
4
0
12
1
0
0
2
1
2
2
3
0
4
1
6
0
0
0
0
9
16
2
0
1
2
0
12
2
4
0
12
1
1
9
4
6
9
9
12
3
16
15
16
9
4
9
0
1
16
9
9
1
9
16
9
12
4
9
2
0
4
0
6
0
3
0
0
0
0...

result:

ok 10000 numbers

Test #3:

score: 0
Accepted
time: 47ms
memory: 3648kb

input:

10000
8 1
8 7
8 6
4 5
8 8
6 6
5 3
6 3
8 6
2 3
1 2
2 2
2 1
4 5
1 3
1 2
2 3
1 1
3 3
8 8
4 3
7 3
1 6
5 4
6 3
2 2
6 7
2 5
1 1
1 1
10 2
4 7
9 7
8 10
5 5
5 1
5 2
4 1
3 5
2 4
5 4
6 3
6 4
2 8
10 5
6 10
6 1
7 2
6 6
8 10
8 3
8 4
5 8
2 5
7 1
5 7
5 8
4 2
2 2
5 3
3 4
3 3
4 4
2 5
1 2
1 1
1 1
5 8
4 3
2 4
5 3
2 3
2...

output:

49
16
0
9
16
0
90
18
56
25
36
4
0
6
56
24
9
24
1
9
0
4
90
6
1
30
30
4
0
0
49
15
30
35
20
9
9
36
16
6
35
4
49
24
81
3
0
12
72
36
30
12
9
36
10
2
30
0
0
0
35
0
1
8
0
0
15
6
0
25
49
0
0
3
1
0
8
16
20
0
36
81
0
3
9
30
8
36
0
25
0
49
16
1
0
16
0
0
0
25
8
0
64
64
0
64
9
6
0
81
45
36
16
0
1
25
49
8
4
2
20
...

result:

ok 10000 numbers

Test #4:

score: 0
Accepted
time: 84ms
memory: 3624kb

input:

10000
11 9
7 5
4 4
4 11
9 7
1 3
9 5
4 9
8 3
7 6
9 7
3 3
4 5
6 2
6 9
2 7
5 9
6 7
8 6
4 7
2 5
6 5
5 8
7 5
6 3
18 1
14 8
17 12
2 11
14 4
8 16
16 1
16 3
3 9
3 2
14 8
6 7
6 16
9 10
9 16
13 1
2 8
9 5
6 2
6 4
5 2
9 7
1 7
7 6
1 7
3 5
1 3
6 4
5 1
5 7
16 7
7 6
6 13
15 7
16 6
8 6
9 1
15 3
18 5
7 17
10 16
16 10...

output:

80
16
20
289
130
144
42
15
169
210
2
36
99
28
144
12
56
169
0
42
36
289
100
70
0
225
81
12
42
4
225
0
12
0
12
168
100
72
289
144
210
100
18
80
110
180
210
0
35
0
64
0
0
130
144
0
40
144
20
0
20
2
121
108
120
132
12
120
42
81
182
9
196
0
0
0
9
99
0
110
132
21
96
0
0
72
8
108
132
25
196
42
221
49
1
72...

result:

ok 10000 numbers

Test #5:

score: 0
Accepted
time: 134ms
memory: 3688kb

input:

10000
17 13
2 9
7 12
1 10
9 15
16 9
10 11
10 4
6 4
10 15
16 13
15 11
11 11
1 12
9 19
9 1
7 2
4 2
4 8
3 9
1 2
3 2
2 8
4 4
3 7
1 7
3 1
9 2
3 4
8 3
2 5
2 3
9 7
8 5
23 25
15 14
14 9
20 17
7 15
20 5
9 22
19 4
1 3
5 18
22 23
17 7
19 5
4 11
22 20
11 4
8 21
7 17
2 12
6 6
11 3
3 14
11 14
3 20
15 5
6 5
27 15
...

output:

130
12
49
272
4
0
342
306
462
8
42
16
143
9
40
0
156
16
234
30
9
126
238
36
0
36
110
441
165
18
30
306
91
121
0
3
225
110
0
48
399
169
0
154
56
8
4
0
18
16
324
117
0
1
9
104
0
120
63
180
288
55
484
81
4
49
288
288
0
169
24
285
1
48
4
54
210
525
0
8
18
78
625
441
18
48
30
90
1
576
225
16
624
304
0
0
...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 181ms
memory: 3652kb

input:

10000
16 17
13 12
13 9
8 10
13 15
10 2
13 7
7 14
2 11
6 9
7 11
1 3
8 7
9 1
6 7
1 11
6 4
14 13
10 3
6 2
9 6
2 3
19 3
1 18
14 4
2 2
16 1
1 2
20 24
15 7
1 16
7 5
15 9
5 8
11 6
18 11
18 17
4 15
2 17
11 5
15 14
20 7
3 13
10 10
7 14
20 3
16 16
17 17
19 17
4 16
17 7
16 14
7 1
31 32
26 6
6 3
7 31
12 18
11 9...

output:

70
49
256
225
72
420
625
0
48
132
0
0
70
112
132
0
24
0
182
8
238
2
342
0
32
0
72
357
0
60
156
399
126
784
72
7
266
25
783
28
208
529
20
104
441
30
255
0
1
725
0
16
324
16
0
0
70
36
2
210
40
224
28
289
484
54
380
255
0
20
1024
221
0
418
81
2
625
420
36
0
0
900
16
378
324
380
182
756
784
378
156
56
0...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 185ms
memory: 3740kb

input:

8195
31 31
10 29
11 22
28 13
18 14
6 17
7 22
1 20
9 14
28 4
17 29
25 10
8 12
21 29
30 16
26 27
28 5
20 5
4 13
1 19
8 2
28 12
3 10
30 27
6 11
8 7
27 23
8 5
4 15
29 13
1 26
11 18
42 19
17 13
5 9
41 30
30 10
4 28
31 14
35 14
13 37
7 23
37 28
2 11
42 19
15 32
31 15
37 24
7 41
35 8
2 38
9 26
22 2
6 20
17...

output:

380
896
400
528
169
506
6
156
77
117
0
196
42
9
676
42
64
42
196
529
1024
132
729
784
44
400
0
30
96
2116
12
108
0
9
650
110
104
56
650
182
9
736
132
840
360
0
756
0
552
176
783
342
575
56
260
900
27
420
624
182
600
120
24
294
756
176
182
195
4
992
180
420
1722
14
400
16
306
6
96
154
440
638
120
104...

result:

ok 8195 numbers

Test #8:

score: 0
Accepted
time: 72ms
memory: 5232kb

input:

36
200 34923
19 6
111 30
122 58
130 123
79 127
51 17
77 115
180 115
135 39
59 17
6 92
164 83
191 61
135 194
21 53
118 131
99 32
115 128
136 73
149 164
80 61
143 172
183 67
178 34
141 11
63 158
198 99
136 181
199 154
51 124
181 143
196 73
129 36
103 26
20 132
113 184
70 21
54 95
151 64
20 85
9 118
31...

output:

0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
39601
39601
39601
39601
0
39601
39601
39601
39601
39601
39601
39601
39601
39601
39601
39601
39601
39601

result:

ok 36 numbers

Test #9:

score: 0
Accepted
time: 74ms
memory: 5936kb

input:

47
300 73618
107 45
10 195
243 73
94 169
32 105
204 216
195 153
120 31
175 135
145 78
234 209
118 28
60 136
231 58
187 136
151 217
176 160
91 269
9 6
62 262
45 37
258 86
54 3
9 71
74 291
180 162
97 238
12 124
205 106
26 48
95 188
25 231
190 208
164 86
202 258
177 102
99 210
259 159
293 269
241 22
9 ...

output:

0
0
0
873
0
0
0
0
89401
0
0
89401
89401
89401
89401
89401
89401
89401
0
89401
89401
89401
89401
89401
89401
89401
89401
89401
1425
89401
89401
89401
89401
89401
89401
89401
89401
89401
89401
89401
89401
89401
2630
89401
89401
89401
46440

result:

ok 47 numbers

Test #10:

score: 0
Accepted
time: 116ms
memory: 8644kb

input:

11
5000 82272
1471 562
571 4062
2376 3538
1758 879
4355 4876
1765 2860
1225 3209
498 1448
589 4453
2795 2625
4702 2777
273 2409
3097 2177
673 1783
734 3503
4990 4311
30 3022
533 2902
4075 431
2471 1295
3584 3647
2082 4048
1501 4783
4753 2661
3844 931
1647 2404
2359 2724
3576 1480
4808 1718
33 4135
7...

output:

0
0
0
0
0
49690
24990001
19470126
24990001
9578925
24990001

result:

ok 11 numbers

Test #11:

score: 0
Accepted
time: 88ms
memory: 10104kb

input:

3
5000 100000
4850 2272
3933 2025
680 4017
1731 2777
4531 3649
604 3731
1982 3943
2572 2993
2689 3809
109 770
375 1878
915 1872
583 1674
801 1824
1372 4181
411 4222
997 2596
1434 4470
2509 4087
659 2740
2748 4217
2424 4669
2604 4588
3965 3636
309 3474
3324 1398
3977 653
4482 2406
1688 2064
3575 634
...

output:

0
0
0

result:

ok 3 number(s): "0 0 0"

Test #12:

score: 0
Accepted
time: 194ms
memory: 16768kb

input:

3
20000 100000
5843 13706
18814 4687
10989 2645
892 6471
5919 3267
14982 10237
3234 13314
12232 1056
17492 12389
10544 4166
1334 15330
7890 19718
1836 7922
4165 4828
9696 3284
18660 10120
6016 3434
14062 9199
19740 11162
19175 17369
13737 3182
11573 977
16960 18709
3875 11593
6079 7904
13185 12275
6...

output:

3185208
3195666
2758896

result:

ok 3 number(s): "3185208 3195666 2758896"

Test #13:

score: 0
Accepted
time: 204ms
memory: 28444kb

input:

2
50000 100000
18349 36288
611 34094
39509 22068
13737 24139
8812 16539
32691 40514
30435 45795
27762 529
44702 5805
39757 39868
38374 6462
638 11003
32821 7502
39027 44967
10477 32684
36221 11712
20354 1895
7172 24249
8283 22070
19281 11370
29093 35378
3778 24398
576 18775
35881 31219
47184 4135
30...

output:

448726135
460334448

result:

ok 2 number(s): "448726135 460334448"

Test #14:

score: 0
Accepted
time: 115ms
memory: 32984kb

input:

3
100000 1
70384 39704
100000 1
40173 62941
100000 1
57956 44429

output:

9999800001
9999800001
9999800001

result:

ok 3 number(s): "9999800001 9999800001 9999800001"

Test #15:

score: 0
Accepted
time: 264ms
memory: 46232kb

input:

2
100000 100000
97142 35673
58757 30367
55923 72614
55158 23354
67397 53241
26699 86278
6870 57884
62293 89093
45762 37900
95133 32337
20986 90171
93467 7731
17953 61135
68736 14892
67506 42592
71949 48847
43288 98525
92346 96229
79284 38280
41392 18856
85050 38517
61551 82312
47956 98863
79913 7625...

output:

3224876460
3231126633

result:

ok 2 number(s): "3224876460 3231126633"

Test #16:

score: 0
Accepted
time: 238ms
memory: 45964kb

input:

2
100000 100000
46395 81745
22228 81651
98590 76796
15598 50394
67488 22778
21214 34195
11489 5442
93015 53334
33703 85678
78450 6720
34843 76187
54984 99888
99562 28301
12154 25162
9797 86024
98250 76151
10721 61304
12287 86339
95384 56394
82981 53310
19047 32305
41067 73852
81678 51522
93027 59381...

output:

3226894740
3220897533

result:

ok 2 number(s): "3226894740 3220897533"

Test #17:

score: 0
Accepted
time: 249ms
memory: 46316kb

input:

2
100000 100000
95649 84714
26916 65639
32746 13682
76037 10138
282 49212
91537 82112
59211 9897
23737 50279
97451 41968
53255 48399
81404 86396
49206 57453
89682 95467
31380 2729
95192 62161
33063 13855
45451 91379
75333 19554
68381 17613
81466 87764
77235 93389
55174 98096
72296 79989
6140 69921
2...

output:

3200670858
3198916512

result:

ok 2 number(s): "3200670858 3198916512"

Test #18:

score: 0
Accepted
time: 177ms
memory: 32924kb

input:

2
49800 100000
40411 14598
25157 29927
19470 10822
27212 44376
44214 12243
11995 3393
2791 2984
16547 47689
2539 23678
14428 46503
23225 12084
18518 12402
20708 33807
16920 38483
40442 40878
1415 42844
24335 42524
35776 4646
33683 34828
33665 49711
47132 34603
29551 24533
47538 4967
47257 23671
5093...

output:

0
0

result:

ok 2 number(s): "0 0"

Test #19:

score: 0
Accepted
time: 183ms
memory: 33348kb

input:

2
49900 100000
9494 36435
2010 15660
17479 30725
12167 26217
19863 45716
10334 40493
41120 29000
28807 5568
8078 35845
14704 4154
18536 48875
7641 9003
32492 6004
10083 37961
23000 15168
38126 29062
18591 32285
24736 9855
20589 40264
10331 16560
35658 17680
22189 35001
5133 22182
13657 9361
20691 33...

output:

0
0

result:

ok 2 number(s): "0 0"

Test #20:

score: 0
Accepted
time: 195ms
memory: 33456kb

input:

2
50000 100000
5231 2791
14965 41569
41168 44545
42262 2379
33211 41289
16288 38430
20832 30238
49342 12810
963 29894
4492 1364
12077 35493
39811 23728
2609 35098
19086 12718
29179 10204
48798 30587
3911 36623
47863 43648
33985 32144
15953 33896
31830 18172
7199 5783
880 27638
47764 35893
36347 3123...

output:

0
0

result:

ok 2 number(s): "0 0"

Test #21:

score: 0
Accepted
time: 189ms
memory: 32004kb

input:

2
50100 100000
30056 9059
47403 41988
41706 44370
49031 47049
3725 29857
6822 8860
24834 42875
2891 39850
45721 5921
26758 14276
33666 25555
48425 32731
18539 3291
41205 18234
45145 34976
41139 45936
46432 35304
27754 5151
21664 5474
37773 13343
40414 40194
25169 13111
34510 27897
46214 8116
6766 69...

output:

0
0

result:

ok 2 number(s): "0 0"

Test #22:

score: 0
Accepted
time: 186ms
memory: 32560kb

input:

2
50200 100000
34110 19659
2383 16161
33495 12468
38334 29397
46106 49642
42217 39286
35325 6078
23667 15477
25890 26928
27068 42145
49082 13232
42933 30802
8591 37008
24930 14414
32369 37393
27028 1024
31740 6065
4941 30077
43727 6312
32743 8127
38064 47738
24091 47290
39476 21365
46596 48959
18547...

output:

0
0

result:

ok 2 number(s): "0 0"

Test #23:

score: 0
Accepted
time: 179ms
memory: 16384kb

input:

3
22500 100000
7120 15367
3928 1008
16458 11949
9347 18804
14453 18016
1284 13991
20310 16232
245 12988
686 12784
10080 14014
18168 18531
1057 2863
10169 4522
11489 9886
16033 21537
9814 19654
576 2163
2380 9562
11722 7984
1382 13770
21667 9926
13034 3929
14747 675
20201 14127
1312 18440
18288 12959...

output:

269977761
270092790
270273596

result:

ok 3 number(s): "269977761 270092790 270273596"

Test #24:

score: 0
Accepted
time: 171ms
memory: 16828kb

input:

3
22500 100000
14321 10787
19164 3467
819 11348
13600 3590
10404 22199
17164 15671
50 8149
20066 981
9903 16537
14189 2732
7947 5823
13142 5772
4301 19724
9133 843
11743 5645
9262 18111
9790 17190
11379 18373
20980 15750
14840 6611
642 22349
10047 7786
16225 19472
9201 22452
4147 15132
9389 9377
631...

output:

237591395
237406455
237961460

result:

ok 3 number(s): "237591395 237406455 237961460"

Test #25:

score: 0
Accepted
time: 198ms
memory: 16828kb

input:

3
22500 100000
688 6657
12725 20892
13023 12555
4489 9173
4888 849
11871 16750
22251 9516
16466 2823
1278 10
9291 8487
974 19123
6929 10696
17503 4988
15288 15930
3414 18822
4857 357
6723 11945
21963 13989
364 12285
22484 13273
14202 15471
1424 21700
16622 19976
14619 16871
13824 5303
21644 14786
16...

output:

206640481
206582985
206928216

result:

ok 3 number(s): "206640481 206582985 206928216"

Test #26:

score: 0
Accepted
time: 192ms
memory: 16944kb

input:

3
22500 100000
9391 14873
8735 17638
7246 21404
3982 12274
7737 20997
6181 2273
11007 4349
21846 7009
7204 15290
21779 1241
9280 944
4048 6056
18858 11511
21651 21638
10635 2848
12849 479
15368 723
15870 12562
13035 9225
13854 4460
21057 20901
8215 16303
18280 12976
6234 12340
20773 8421
16196 14589...

output:

177035824
176969805
176570775

result:

ok 3 number(s): "177035824 176969805 176570775"

Test #27:

score: 0
Accepted
time: 193ms
memory: 17228kb

input:

3
22500 100000
18911 7789
17178 1754
5591 13894
21182 13448
5126 12247
4185 8466
21633 13178
21492 8024
7310 21870
9623 3459
2035 16965
21449 4438
5233 13119
13832 3888
19743 20995
1907 19302
7417 14361
19104 4434
14077 20897
15130 4014
14953 21668
628 13865
17894 15714
628 5846
7668 21538
7994 1914...

output:

148388732
147524740
148193970

result:

ok 3 number(s): "148388732 147524740 148193970"

Test #28:

score: 0
Accepted
time: 187ms
memory: 17188kb

input:

3
25000 100000
1139 12204
13088 3946
1173 16637
6862 5563
675 6160
13801 24093
14202 23266
7523 15381
12135 19164
19242 15184
8002 13427
12610 1228
24016 15578
10246 13058
21430 20589
5913 15550
9677 14521
7832 16920
18978 9581
24762 11699
24130 15833
7808 10425
20541 8939
723 11526
14494 16285
1142...

output:

358666776
358931970
358685712

result:

ok 3 number(s): "358666776 358931970 358685712"

Test #29:

score: 0
Accepted
time: 187ms
memory: 17528kb

input:

3
25000 100000
22201 23681
3268 11991
17840 18878
19556 3796
9214 7222
5758 24053
21966 5511
7516 3174
11845 15318
22547 681
11113 1276
4181 9537
23705 9610
3268 428
18074 15286
1456 24988
1127 2190
6366 20123
9240 1211
1740 18700
11004 13571
11870 17447
16899 18851
19537 4632
18595 1451
19144 5636
...

output:

321090497
321323548
321305600

result:

ok 3 number(s): "321090497 321323548 321305600"

Test #30:

score: 0
Accepted
time: 180ms
memory: 17864kb

input:

3
25000 100000
6460 9228
4315 15691
2667 6148
6321 22725
939 8010
19587 1319
24515 10526
19453 21565
11577 16634
9941 18496
353 15297
441 3046
598 16987
6898 6219
12466 20957
8586 15
7296 13591
17619 4578
2567 18254
9362 24007
11483 11674
16463 9560
8756 19243
1949 7464
3407 24679
14707 5077
6695 70...

output:

284124567
284529408
284444628

result:

ok 3 number(s): "284124567 284529408 284444628"

Test #31:

score: 0
Accepted
time: 212ms
memory: 18804kb

input:

3
27500 100000
407 6837
10728 9698
25825 11248
26329 24720
4984 13924
26699 14563
2904 1492
20750 8673
26560 16307
17737 11530
20524 11935
17516 7563
19218 24273
3596 9736
20926 18336
5614 9335
1944 1330
21795 23233
1287 24212
9202 17416
1454 14910
16037 22029
3241 10049
7088 9597
20128 27346
10109 ...

output:

294362549
295082595
294259595

result:

ok 3 number(s): "294362549 295082595 294259595"

Test #32:

score: 0
Accepted
time: 104ms
memory: 12904kb

input:

3
15000 100000
2139 13160
14913 953
2139 2103
8920 953
4034 11854
10434 4027
4034 4749
533 4027
5153 13180
3729 10000
5153 3647
551 10000
10434 11634
13827 1716
10434 5667
12951 1716
12338 2354
3081 6277
12338 12499
14674 6277
3490 6363
8252 4326
3490 8841
1477 4326
5588 1807
11926 11282
5588 644
17...

output:

216090000
216090000
216090000

result:

ok 3 number(s): "216090000 216090000 216090000"

Test #33:

score: 0
Accepted
time: 110ms
memory: 15320kb

input:

3
20000 100000
11160 6663
4811 267
11160 19896
17208 267
6490 2046
5301 16534
6490 3639
14215 16534
5259 3838
2529 7792
5259 5991
5909 7792
9057 611
19729 15893
9057 16709
253 15893
15132 1089
14698 5489
15132 9094
4682 5489
16831 3345
5909 10469
16831 69
7139 10469
6172 3832
18393 2037
6172 13565
1...

output:

392040000
392040000
392040000

result:

ok 3 number(s): "392040000 392040000 392040000"

Test #34:

score: 0
Accepted
time: 124ms
memory: 16712kb

input:

3
25000 100000
15961 6571
5616 16506
15961 19393
2083 16506
5735 20962
20565 13627
5735 2705
15481 13627
17046 5443
10805 15633
17046 23402
17240 15633
748 5505
136 2705
748 946
10438 2705
6082 17836
20129 7258
6082 1574
18286 7258
17008 24383
21783 20962
17008 9177
4311 20962
11489 1574
9421 22809
...

output:

620010000
620010000
620010000

result:

ok 3 number(s): "620010000 620010000 620010000"

Test #35:

score: 0
Accepted
time: 152ms
memory: 16304kb

input:

3
20000 100000
16281 13983
3476 9370
4296 16908
14288 2560
767 2720
10932 12995
5400 19500
13246 9460
14844 19112
8412 14487
5768 10566
1973 19089
6335 2434
12220 7677
10680 9229
13530 4279
9981 2642
11994 6154
10563 18202
17229 19743
12094 7539
17516 15661
7020 4532
2524 1753
10443 2221
17440 11827...

output:

32100000
32100000
31340775

result:

ok 3 number(s): "32100000 32100000 31340775"

Test #36:

score: 0
Accepted
time: 183ms
memory: 15920kb

input:

3
20000 100000
765 8478
18038 10003
9482 12015
16385 1444
2779 17290
18021 3883
17643 3517
1096 18619
2555 14237
9817 3455
18350 2883
9639 4888
17750 3198
13788 217
16901 17297
14173 14541
9020 4951
10648 10148
13381 9884
17255 2717
10463 3368
17441 12978
1953 15232
2002 10398
14324 19045
17658 5925...

output:

31813052
32860000
31840000

result:

ok 3 number(s): "31813052 32860000 31840000"

Extra Test:

score: 0
Extra Test Passed