oj.uz

Submission #252146

# Submission time Handle Problem Language Result Execution time Memory
252146 2020-07-24T10:23:35 Z Erkhemkhuu Bridges (APIO19_bridges) C++17
13 / 100
 101 ms 48768 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
const ll N = 1005;
bool vis[N];
tuple <ll, ll, ll> brid[N];
vector <vector <ll> > adj(N);
vector <ll> wp[N][N];
ll dfs(ll v, ll w) {
    ll ans = 1;
    vis[v] = true;
    for(auto &u: adj[v])
        for(auto &x: wp[v][u])
            if(!vis[u] && w <= x) ans += dfs(u, w);
    return ans;
}
int main() {
    ll n, m, i, v, u, w, q, t, l, r;
    cin >> n >> m;
    for(i = 0; i < m; i++) {
        cin >> v >> u >> w;
        v--; u--;
        adj[v].pb(u);
        adj[u].pb(v);
        wp[v][u].pb(w);
        wp[u][v].pb(w);
        brid[i] = {v, u, wp[v][u].size() - 1};
    }
    cin >> q;
    while(q--) {
        cin >> t >> l >> r;
        l--;
        if(t == 1) {
            auto temp = brid[l];
            ll x = get <0> (temp);
            ll y = get <1> (temp);
            ll z = get <2> (temp);
            wp[x][y][z] = wp[y][x][z] = r;
        }
        else {
            memset(vis, false, sizeof(vis));
            cout << dfs(l, r) << "\n";
        }
    }
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24064 KB Output is correct
2 Correct 13 ms 24064 KB Output is correct
3 Correct 101 ms 24192 KB Output is correct
4 Correct 44 ms 24064 KB Output is correct
5 Correct 37 ms 24064 KB Output is correct
6 Correct 40 ms 24064 KB Output is correct
7 Correct 34 ms 24064 KB Output is correct
8 Correct 38 ms 24064 KB Output is correct
9 Correct 35 ms 24064 KB Output is correct
10 Correct 38 ms 24064 KB Output is correct
11 Correct 40 ms 24064 KB Output is correct
12 Correct 39 ms 24064 KB Output is correct
13 Correct 39 ms 24064 KB Output is correct
14 Correct 41 ms 24064 KB Output is correct
15 Correct 39 ms 24064 KB Output is correct
16 Correct 38 ms 24064 KB Output is correct
17 Correct 34 ms 24064 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 48768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 48760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 48504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 48768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 24064 KB Output is correct
2 Correct 13 ms 24064 KB Output is correct
3 Correct 101 ms 24192 KB Output is correct
4 Correct 44 ms 24064 KB Output is correct
5 Correct 37 ms 24064 KB Output is correct
6 Correct 40 ms 24064 KB Output is correct
7 Correct 34 ms 24064 KB Output is correct
8 Correct 38 ms 24064 KB Output is correct
9 Correct 35 ms 24064 KB Output is correct
10 Correct 38 ms 24064 KB Output is correct
11 Correct 40 ms 24064 KB Output is correct
12 Correct 39 ms 24064 KB Output is correct
13 Correct 39 ms 24064 KB Output is correct
14 Correct 41 ms 24064 KB Output is correct
15 Correct 39 ms 24064 KB Output is correct
16 Correct 38 ms 24064 KB Output is correct
17 Correct 34 ms 24064 KB Output is correct
18 Runtime error 38 ms 48768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Halted 0 ms 0 KB -