oj.uz

Submission #522221

# Submission time Handle Problem Language Result Execution time Memory
522221 2022-02-04T07:39:31 Z Aldas25 Bridges (APIO19_bridges) C++14
27 / 100
 3000 ms 10432 KB 
#include <bits/stdc++.h>

using namespace std;

#define FAST_IO ios_base::sync_with_stdio(0); cin.tie(nullptr)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<ll> vl;

const int MAXN = 500100;

int par[MAXN], sz[MAXN];
int find (int a) {return par[a] = par[a]==a ? a : find(par[a]);}
bool same (int a, int b) {return find(a) == find(b);}
void unite (int a, int b) {
    a = find(a);
    b = find(b);
    if (a==b) return;
    par[b] = a;
    sz[a] += sz[b];
}


int n, m, q;

void dsuReset () {
    FOR(i, 0, n) {
        par[i] = i;
        sz[i] = 1;
    }
}

int ui[MAXN], vei[MAXN], di[MAXN];
int ti[MAXN], ai[MAXN], bi[MAXN];

vector<pair<int, pii>> edges;

int ans[MAXN];
vector<pair<pii, int>> queries;

void solve4 () {
    dsuReset();

    FOR(i, 1, m) {
        edges.pb({di[i], {ui[i], vei[i]}});
    }

    sort(edges.begin(), edges.end());
    reverse(edges.begin(), edges.end());

    FOR(i, 1, q) {
        if (ti[i] == 2) {
            queries.pb({{bi[i], ai[i]}, i});
        }
    }

    sort(queries.begin(), queries.end());
    reverse(queries.begin(), queries.end());

    int qId = 0, eId = 0;

    while (qId < (int)queries.size()) {
        if (eId < m && edges[eId].f >= queries[qId].f.f) {
            int u = edges[eId].s.f;
            int v = edges[eId].s.s;
            unite(u,v);
            eId++;
        } else {
            int v = queries[qId].f.s;
            int id = queries[qId].s;
            ans[id] = sz[find(v)];
            qId++;
        }
    }

    FOR(i, 1, q) if (ti[i] == 2) cout << ans[i] << "\n";
}

void solve1 () {
    FOR(i, 1, q) {
        if (ti[i] == 1) {
            int id = ai[i];
            int newW = bi[i];
            di[id] = newW;
        } else {
            dsuReset();

            int v = ai[i];
            int w = bi[i];

            FOR(j, 1, m) {
                if (di[j] >= w)
                    unite (ui[j], vei[j]);
            }

            cout << sz[find(v)] << "\n";
        }
    }
}

int main()
{
    FAST_IO;

    cin >> n >> m;
    FOR(i, 1, m)
        cin >> ui[i] >> vei[i] >> di[i];

    cin >> q;
    FOR(i, 1, q) {
        cin >> ti[i] >> ai[i] >> bi[i];
    }

    bool sub4 = true;
    FOR(i, 1, q) if (ti[i] != 2) sub4 = false;

    if (sub4)
        solve4();
    else
        solve1();

    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 45 ms 520 KB Output is correct
4 Correct 4 ms 780 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 6 ms 460 KB Output is correct
8 Correct 7 ms 460 KB Output is correct
9 Correct 8 ms 460 KB Output is correct
10 Correct 6 ms 460 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 7 ms 460 KB Output is correct
13 Correct 11 ms 528 KB Output is correct
14 Correct 10 ms 444 KB Output is correct
15 Correct 10 ms 460 KB Output is correct
16 Correct 8 ms 460 KB Output is correct
17 Correct 7 ms 460 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 2528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 2196 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 8248 KB Output is correct
2 Correct 40 ms 4832 KB Output is correct
3 Correct 38 ms 5180 KB Output is correct
4 Correct 42 ms 5204 KB Output is correct
5 Correct 73 ms 8868 KB Output is correct
6 Correct 82 ms 10320 KB Output is correct
7 Correct 72 ms 8868 KB Output is correct
8 Correct 60 ms 7604 KB Output is correct
9 Correct 60 ms 7756 KB Output is correct
10 Correct 61 ms 7608 KB Output is correct
11 Correct 71 ms 9144 KB Output is correct
12 Correct 75 ms 9200 KB Output is correct
13 Correct 68 ms 9048 KB Output is correct
14 Correct 74 ms 8812 KB Output is correct
15 Correct 70 ms 8840 KB Output is correct
16 Correct 86 ms 10432 KB Output is correct
17 Correct 85 ms 10272 KB Output is correct
18 Correct 84 ms 10376 KB Output is correct
19 Correct 79 ms 10324 KB Output is correct
20 Correct 77 ms 9296 KB Output is correct
21 Correct 72 ms 9272 KB Output is correct
22 Correct 80 ms 9936 KB Output is correct
23 Correct 63 ms 8132 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3069 ms 2528 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 45 ms 520 KB Output is correct
4 Correct 4 ms 780 KB Output is correct
5 Correct 6 ms 460 KB Output is correct
6 Correct 5 ms 460 KB Output is correct
7 Correct 6 ms 460 KB Output is correct
8 Correct 7 ms 460 KB Output is correct
9 Correct 8 ms 460 KB Output is correct
10 Correct 6 ms 460 KB Output is correct
11 Correct 6 ms 460 KB Output is correct
12 Correct 7 ms 460 KB Output is correct
13 Correct 11 ms 528 KB Output is correct
14 Correct 10 ms 444 KB Output is correct
15 Correct 10 ms 460 KB Output is correct
16 Correct 8 ms 460 KB Output is correct
17 Correct 7 ms 460 KB Output is correct
18 Execution timed out 3069 ms 2528 KB Time limit exceeded
19 Halted 0 ms 0 KB -