Submission #983167

#	Time	Username	Problem	Language	Result	Execution time	Memory
983167		vjudge1	Bridges (APIO19_bridges)	C++17	13 / 100	106 ms	11164 KiB

bridges

#include <time.h>
#include <cstdlib>
#include <stack>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <map>
#include <set>
#include <iterator>
#include <deque>
#include <queue>
#include <sstream>
#include <array>
#include <string>
#include <tuple>
#include <chrono>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <list>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <bitset>
#define ll long long
using namespace std;

int tt = 1, n, m;
ll a[200001], b[200001], c[200001];
vector<pair<int, ll>> g[200005];
bool us[200005];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= m; i++)
        cin >> a[i] >> b[i] >> c[i];
    cin >> tt;
    if(n <= 1000 && m <= 1000 && tt <= 10000){
        for(int i = 1; i <= tt; i++){
            int type;
            cin >> type;
            if(type == 1){
                ll p, num;
                cin >> p >> num;
                c[p] = num; 
            }
            else{
                ll x, w;
                cin >> x >> w; 
                queue<int> q;
                for(int i = 1; i <= n; i++){
                    g[i].clear();
                    us[i] = 0;
                }
                for(int i = 1; i <= m; i++){
                    g[a[i]].push_back({b[i], c[i]});
                    g[b[i]].push_back({a[i], c[i]});
                }
                q.push(x);
                us[x] = 1;
                int kol = 1;
                while(!q.empty()){
                    int d = q.front();
                    q.pop();
                    for(auto to : g[d]){
                        if(!us[to.first] && to.second >= w){
                            kol++;
                            us[to.first] = 1;
                            q.push(to.first);
                        }
                    }
                }
                cout << kol << "\n";
            }
        }
    }
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 16
• Subtask 3: 0 / 17
• Subtask 4: 0 / 14
• Subtask 5: 0 / 13
• Subtask 6: 0 / 27