oj.uz

Submission #253543

# Submission time Handle Problem Language Result Execution time Memory
253543 2020-07-28T07:47:48 Z SorahISA Bridges (APIO19_bridges) C++17
14 / 100
 118 ms 8020 KB 
#include <bits/stdc++.h>
using namespace std;

#define int int64_t
#define double long double
using pii = pair<int, int>;
template<typename T>
using Prior = priority_queue<T>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back
#define fastIO() ios_base::sync_with_stdio(false), cin.tie(0)

struct Edge {
    int u, v, w;
};

struct Query {
    int op, st, wi, ti;
};

const int maxn = 5E4 + 5;
const int INF = 0x7f7f7f7f;

vector<int> par(maxn), sz(maxn, 1);

int R(int x) {return x ^ par[x] ? par[x] = R(par[x]) : x;}
void U(int x, int y) {if (R(x) != R(y)) sz[par[y]] += sz[par[x]], par[par[x]] = par[y];}

int32_t main() {
    fastIO();
    iota(ALL(par), 0);
    
    int n, m, Q, tok = 0;
    cin >> n >> m;
    
    vector<Edge> edge(m);
    for (auto &e : edge) cin >> e.u >> e.v >> e.w;
    sort(ALL(edge), [](auto e1, auto e2) {return e1.w > e2.w;});
    edge.pb({0, 0, 0});
    
    cin >> Q;
    
    vector<Query> query(Q);
    for (auto &q : query) cin >> q.op >> q.st >> q.wi, q.ti = tok++;
    sort(ALL(query), [](auto q1, auto q2) {return q1.wi > q2.wi;});
    
    vector<int> ans(Q);
    int tokE = 0, tokQ = 0;
    while (tokQ < Q) {
        if (edge[tokE].w >= query[tokQ].wi) {
            U(edge[tokE].u, edge[tokE].v), ++tokE;
        }
        else {
            ans[query[tokQ].ti] = sz[R(query[tokQ].st)], ++tokQ;
        }
    }
    
    for (auto x : ans) cout << x << "\n";
    
    return 0;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 6372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 6008 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 110 ms 7832 KB Output is correct
2 Correct 45 ms 5240 KB Output is correct
3 Correct 48 ms 5752 KB Output is correct
4 Correct 48 ms 5752 KB Output is correct
5 Correct 81 ms 7888 KB Output is correct
6 Correct 109 ms 7888 KB Output is correct
7 Correct 83 ms 7944 KB Output is correct
8 Correct 76 ms 6372 KB Output is correct
9 Correct 78 ms 6432 KB Output is correct
10 Correct 79 ms 6564 KB Output is correct
11 Correct 92 ms 7064 KB Output is correct
12 Correct 92 ms 7064 KB Output is correct
13 Correct 99 ms 7320 KB Output is correct
14 Correct 81 ms 8020 KB Output is correct
15 Correct 85 ms 7892 KB Output is correct
16 Correct 109 ms 7800 KB Output is correct
17 Correct 114 ms 7784 KB Output is correct
18 Correct 115 ms 7772 KB Output is correct
19 Correct 118 ms 7772 KB Output is correct
20 Correct 100 ms 7636 KB Output is correct
21 Correct 97 ms 7564 KB Output is correct
22 Correct 104 ms 7872 KB Output is correct
23 Correct 76 ms 7572 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 6372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1152 KB Output isn't correct
2 Halted 0 ms 0 KB -