Submission #933995

#	Time	Username	Problem	Language	Result	Execution time	Memory
933995		leo_2727	Bridges (APIO19_bridges)	C++17	13 / 100	3090 ms	7504 KiB

bridges

#include <algorithm>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <iostream>
#include <cmath>
#include <queue>
#include <set>
#include <cstring>
#include <map>
#include <unordered_map>
#define F first
#define S second
#define PB push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<pair<int, ii>> viii;
typedef vector<vii> vvii;
typedef vector<ll> vll;
typedef vector<vll> vvll;

int n, m;
vector<pair<ii, int>> bridges;
vvii al;
bool vis[50005];

void dfs(int node, int w){
    if(vis[node])   return;
    vis[node]=true;
    for(auto ch:al[node])
        if(ch.S>=w)
            dfs(ch.F, w);
}

int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>m;
    al.resize(n+1, vii ());
    bridges.resize(m+1);
    for(int i=1;i<=m;i++){
        int x, y, w;
        cin>>x>>y>>w;
        al[x].PB({y, w});
        al[y].PB({x, w});
        bridges[i]={{x, y}, w};
    }
    int q;  cin>>q;
    while(q--){
        int type, x, y;
        cin>>type>>x>>y;
        if(type==1){
            int a=bridges[x].F.F, b=bridges[x].F.S, w=bridges[x].S;
            bridges[x]={{a, b}, y};
            for(int i=0;i<(int)al[a].size();i++){
                if(al[a][i].F==b && al[a][i].S==w){
                    al[a][i]={b, y};
                    break;
                }
            }
            for(int i=0;i<(int)al[b].size();i++){
                if(al[b][i].F==a && al[b][i].S==w){
                    al[b][i]={a, y};
                    break;
                }
            }
        }
        else{
            memset(vis, false, n+1);
            dfs(x, y);
            int ans=0;
            for(int i=1;i<=n;i++)
                if(vis[i])
                    ans++;
            cout<<ans<<"\n";
        }
    }
    return 0;
}

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