Submission #267097

#	Time	Username	Problem	Language	Result	Execution time	Memory
267097		kimbj0709	Bridges (APIO19_bridges)	C++14	13 / 100	3068 ms	18176 KiB

bridges

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 50050
#define f first
#define s second
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    vector<multiset<pair<int,int> > > adj(maxn);
    int n,m,q;
    int input1,input2,input3;
    vector<pair<int,pair<int,int> > > edges;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> input1 >> input2 >> input3;
        edges.push_back({input1,{input2,input3}});
        adj[input1].insert({input2,input3});
        adj[input2].insert({input1,input3});
    }
    cin >> q;
    for(int i=0;i<q;i++){
        cin >> input1 >> input2 >> input3;
        if(input1==1){//update
            input2--;
            auto k = adj[edges[input2].f].find({edges[input2].s.f,edges[input2].s.s});
            auto j = adj[edges[input2].s.f].find({edges[input2].f,edges[input2].s.s});
            adj[edges[input2].f].erase(k);
            adj[edges[input2].s.f].erase(j);
            edges[input2].s.s = input3;
            adj[edges[input2].s.f].insert({edges[input2].f,edges[input2].s.s});
            adj[edges[input2].f].insert({edges[input2].s.f,edges[input2].s.s});
        }
        else{
            vector<int> visited(maxn,0);
            deque<int> q1;
            q1.push_back(input2);
            visited[input2] = 1;
            while(q1.size()!=0){
                int a = q1.front();
                q1.pop_front();
                for(auto k:adj[a]){
                    if(k.s<input3){
                        continue;
                    }
                    //cout << k.s << " " << input2 << "--\n";
                    if(visited[k.f]==0){
                        visited[k.f] = 1;
                        q1.push_back(k.f);
                    }
                }
            }
            int ans = 0;
            for(auto k:visited){
                ans += k;
            }
            cout << ans << "\n";
        }
        //cout << i << "--" << endl;
    }
}

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