oj.uz

Submission #774684

# Submission time Handle Problem Language Result Execution time Memory
774684 2023-07-06T01:45:19 Z That_Salamander Bridges (APIO19_bridges) C++14
13 / 100
 3000 ms 14100 KB 
#include <bits/stdc++.h>
#define int long long

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

int n, m, q;
vector<pair<int, int>> conn[100000];
pair<pair<int, int>, pair<int, int>> edges[100000];

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;

    FOR (i, m) {
        int u, v, d;
        cin >> u >> v >> d;

        u--; v--;

        edges[i] = {
            {u, conn[u].size()},
            {v, conn[v].size()}
        };

        conn[u].push_back({v, d});
        conn[v].push_back({u, d});
    }

    cin >> q;

    FOR(i, q) {
        int t;
        cin >> t;

        if (t == 1) {
            int b, r;
            cin >> b >> r;

            b--;

            conn[edges[b].first.first][edges[b].first.second].second = r;
            conn[edges[b].second.first][edges[b].second.second].second = r;
        } else {
            int s, w;
            cin >> s >> w;

            s--;

            vector<bool> visited(100000);
            queue<int> q;
            q.push(s);
            int res = 0;

            while (q.size()) {
                int x = q.front(); q.pop();
                if (visited[x])continue;
                visited[x] = true;
                res++;

                for (auto c: conn[x]) {
                    if (c.second >= w) {
                        q.push(c.first);
                    }
                }
            }


            cout << res << endl;
        }
    }
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 76 ms 2948 KB Output is correct
4 Correct 16 ms 2772 KB Output is correct
5 Correct 15 ms 2848 KB Output is correct
6 Correct 13 ms 2772 KB Output is correct
7 Correct 13 ms 2772 KB Output is correct
8 Correct 12 ms 2772 KB Output is correct
9 Correct 14 ms 2772 KB Output is correct
10 Correct 11 ms 2772 KB Output is correct
11 Correct 10 ms 2772 KB Output is correct
12 Correct 10 ms 2772 KB Output is correct
13 Correct 14 ms 2860 KB Output is correct
14 Correct 12 ms 2772 KB Output is correct
15 Correct 14 ms 2860 KB Output is correct
16 Correct 17 ms 2688 KB Output is correct
17 Correct 16 ms 2780 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 9660 KB Output is correct
2 Correct 112 ms 9308 KB Output is correct
3 Correct 114 ms 9300 KB Output is correct
4 Correct 238 ms 9460 KB Output is correct
5 Correct 250 ms 9596 KB Output is correct
6 Execution timed out 3063 ms 8276 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 996 ms 8152 KB Output is correct
2 Correct 2441 ms 5036 KB Output is correct
3 Execution timed out 3082 ms 6944 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 9660 KB Output is correct
2 Correct 112 ms 9308 KB Output is correct
3 Correct 114 ms 9300 KB Output is correct
4 Correct 238 ms 9460 KB Output is correct
5 Correct 250 ms 9596 KB Output is correct
6 Execution timed out 3063 ms 8276 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 1 ms 2644 KB Output is correct
3 Correct 76 ms 2948 KB Output is correct
4 Correct 16 ms 2772 KB Output is correct
5 Correct 15 ms 2848 KB Output is correct
6 Correct 13 ms 2772 KB Output is correct
7 Correct 13 ms 2772 KB Output is correct
8 Correct 12 ms 2772 KB Output is correct
9 Correct 14 ms 2772 KB Output is correct
10 Correct 11 ms 2772 KB Output is correct
11 Correct 10 ms 2772 KB Output is correct
12 Correct 10 ms 2772 KB Output is correct
13 Correct 14 ms 2860 KB Output is correct
14 Correct 12 ms 2772 KB Output is correct
15 Correct 14 ms 2860 KB Output is correct
16 Correct 17 ms 2688 KB Output is correct
17 Correct 16 ms 2780 KB Output is correct
18 Correct 123 ms 9660 KB Output is correct
19 Correct 112 ms 9308 KB Output is correct
20 Correct 114 ms 9300 KB Output is correct
21 Correct 238 ms 9460 KB Output is correct
22 Correct 250 ms 9596 KB Output is correct
23 Execution timed out 3063 ms 8276 KB Time limit exceeded
24 Halted 0 ms 0 KB -