oj.uz

Submission #447500

# Submission time Handle Problem Language Result Execution time Memory
447500 2021-07-26T15:16:34 Z K4YAN Bridges (APIO19_bridges) C++17
0 / 100
 3000 ms 9084 KB 
//Be Name Khoda
// 08:55 - 19:30 -> ta 8:25

#include<bits/stdc++.h>
#pragma GCC optimize ("unroll-loops")

using namespace std;

typedef long long ll;
typedef long double ld;
#define all(x) x.begin(), x.end()
#define pll pair<ll, ll>
#define pii pair<int, int>
#define plll pair<pll, ll>
#define piii pair<pii, int>
#define piiii pair<pii, pii>

const int mxn = 5e4 + 16;
int n, m, q, u, v, w, t;
int eg[2 * mxn][3];
vector<pii> adj[mxn];
bool mark[mxn];

int bs(int v, int u, int w, int l, int r) {

    if(r - l == 1) {
        return l;
    }
    int m = (l + r) >> 1;
    if(adj[v][m].first == u && adj[v][m].second == w) return m;
    if(adj[v][m] < make_pair(u, w)) {
        return bs(v, u, w, m + 1, r);
    }
    else {
        return bs(v, u, w, l, m);
    }

}

int BFS(int v, int w) {

    fill(mark, mark + mxn, false);
    mark[v] = 1;
    vector<int> a;
    a.push_back(v);
    int p = 0, x;

    while(p < int(a.size())) {
        x = a[p++];
        for(auto U : adj[x]) {
            if(mark[U.first] == false && U.second >= w) {
                a.push_back(U.first);
                mark[U.first] = 1;
            }
        }
    }
    return int(a.size());

}

void input() {

    cin >> n >> m;
    for(int i = 0; i < m; i++) {
        cin >> v >> u >> w;
        adj[v].push_back({u, w});
        adj[u].push_back({v, w});
        eg[i + 1][0] = v, eg[i + 1][1] = u, eg[i + 1][2] = w;
    }
    cin >> q;

}

void solve() {

    for(int i = 0; i <= n; i++) {
        sort(all(adj[i]));
    }
    for(int i = 0; i < q; i++) {
        cin >> t;
        if(t == 1) {
            cin >> t >> w;
            adj[eg[t][0]][bs(eg[t][0], eg[t][1], eg[t][2], 0, int(adj[eg[t][0]].size()))].second = w;
            adj[eg[t][1]][bs(eg[t][1], eg[t][0], eg[t][2], 0, int(adj[eg[t][1]].size()))].second = w;
        } 
        else {
            cin >> v >> w;
            cout << BFS(v, w) << endl;
        }
    }

}

int main() {

    ios_base::sync_with_stdio(false);

    input(), solve();

    return 0;

}
/*
3 4
1 2 5
2 3 2
3 1 4
2 3 8
5
2 1 5
1 4 1
2 2 5
1 1 1
2 3 2
*/

Subtask #1
0 / 13.0

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

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3075 ms 4936 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 3071 ms 5276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

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

Subtask #5
0 / 13.0

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

Subtask #6
0 / 27.0

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