Submission #409314

#TimeUsernameProblemLanguageResultExecution timeMemory
409314Blistering_BarnaclesBridges (APIO19_bridges)C++11
13 / 100
3068 ms24536 KiB
//apig's property
//Happiness can be found, even in the darkest of times, if one only remembers to turn on the light
//El Pueblo Unido Jamas Sera Vencido
//The saddest thing about betrayal? is that it never comes from your enemies
//Do or do not... there is no try
//Billions of bilious blue blistering barnacles in a thundering typhoon!
#include<bits/stdc++.h>
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define F first
#define S second
#define pb push_back
#define vll vector< ll >
#define vi vector< int >
#define pll pair< ll , ll >
#define pi pair< int , int >
#define all(s) s.begin() , s.end()
#define sz(s) s.size()
#define str string
#define md ((s + e) / 2)
#define mid ((l + r) / 2)
#define msdp(dp) memset(dp , -1 , sizeof dp)
#define mscl(dp) memset(dp , 0 , sizeof dp)
#define C continue
#define R return
#define B break
#define lx node * 2
#define rx node * 2 + 1
#define br(o) o ; break
#define co(o) o ; continue
using namespace std;
typedef long long ll;
ll q, dp[105][100005], a[555555] , vis[555555], k, l, m, n, o, p;
map < ll , ll > mp;
vector < pair < pll , ll > > adj[555555];
const ll mod = 1e9+7;
str s;
pll pr[555555] ;
void dfs(ll v , ll par , ll w){
    vis[v] = 1 ;
    for(auto u : adj[v]){
        if(u.F.F == par || u.F.S < w || vis[u.F.F])C ;
        dfs(u.F.F , v , w) ;
    }
}
void solve(){
    cin >> n >> m ;
    for(ll i = 1 ; i <= m ; i++){
        cin >> o >> p >> k ;
        adj[o].pb( { { p , k } , i } ) ;
        adj[p].pb( { { o , k } , i } ) ;
        pr[i] = {o , p} ;
    }
    ll cnt = 0 ;
    cin >> l ;
    while(l--){
        cin >> k ;
        if(k == 2){
            cin >> o >> p ;
            for(ll i = 1 ; i <= n ; i++)vis[i] = 0 ;
            dfs(o , 0 , p) ;
            ll ans = 0 ;
            for(ll i =  1; i <= n; i++)ans += vis[i] ;
            cout << ans << endl ;

        }
        else {
            cin >> o >> p ;
            pll op = pr[o] ;
            for(ll i = 0 ; i < adj[op.F].size() ; i++){
                if(adj[op.F][i].S == o){
                    adj[op.F][i].F.S = p ;
                    B ;
                }
            }
            //for(auto u : adj[op.F]) cout << u.F.F << " " << u.F.S << " " << u.S << endl ;
            for(ll i = 0 ; i < sz(adj[op.S]) ; i++){
                if(adj[op.S][i].S == o){
                    adj[op.S][i].F.S = p ;
                    B ;
                }
            }
        }
    }
}
int main(){
    fast ;
    //cin >> q;
    q = 1;
    while(q--){
        solve();
    }
}

Compilation message (stderr)

bridges.cpp: In function 'void solve()':
bridges.cpp:69:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             for(ll i = 0 ; i < adj[op.F].size() ; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~
bridges.cpp:76:30: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |             for(ll i = 0 ; i < sz(adj[op.S]) ; i++){
      |                              ^
bridges.cpp:53:8: warning: unused variable 'cnt' [-Wunused-variable]
   53 |     ll cnt = 0 ;
      |        ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...