Submission #1361917

#TimeUsernameProblemLanguageResultExecution timeMemory
1361917MunkhturErdenebatBridges (APIO19_bridges)C++20
0 / 100
38 ms6980 KiB
#include<bits/stdc++.h>
#include<string.h>
#include <algorithm>
#include <iterator>
#include <set>
#include <stdlib.h>
 #define ll long long
 #define fr first
 #define sc second
 #define pb push_back
 #define YES cout<<"YES"<<endl
 #define NO cout<<"NO"<<endl
 #define endl "\n"
using namespace std;
    ll a,b,c,d,e,f,m,i,j,n,h,g,mid,l,r,ka,dp[200005],q[200005],t[205005];
    map<ll,ll> mee,see;
    map<ll,ll> mii;
    vector<ll> vas[20005],ves,maa[1001000];
    string x,y,z,te,to;
    pair<ll,ll> wefe,k[200105];
    stack<ll> munkh;
    multiset<ll> mul;
int main(){
    cin>>a>>b;
    for(i=0 ; i<b ; i++){
        cin>>k[i].fr>>k[i].sc>>q[i];
        vas[k[i].fr].pb(k[i].sc);
        vas[k[i].sc].pb(k[i].fr);
        maa[k[i].fr*1000+k[i].sc].pb(q[i]);
        maa[k[i].sc*1000+k[i].fr].pb(q[i]);
        sort(maa[k[i].sc*1000+k[i].fr].begin(),maa[k[i].sc*1000+k[i].fr].end());
        sort(maa[k[i].fr*1000+k[i].sc].begin(),maa[k[i].fr*1000+k[i].sc].end());
    }
    
    ll ka;
    cin>>ka;
    while(ka--){
        cin>>b;
        if(b==1){
            cin>>c>>d;
            for(i=0 ; i<maa[k[c-1].sc*1000+k[c-1].fr].size() ; i++){
                if(maa[k[c-1].sc*1000+k[c-1].fr][i]==q[c-1]){
                    maa[k[c-1].sc*1000+k[c-1].fr][i]=d;
                    break;
                }
            }
            for(i=0 ; i<maa[k[c-1].fr*1000+k[c-1].sc].size() ; i++){
                if(maa[k[c-1].fr*1000+k[c-1].sc][i]==q[c-1]){
                    maa[k[c-1].fr*1000+k[c-1].sc][i]=d;
                    break;
                }
            }
            sort(maa[k[c-1].sc*1000+k[c-1].fr].begin(),maa[k[c-1].sc*1000+k[c-1].fr].end());
            sort(maa[k[c-1].fr*1000+k[c-1].sc].begin(),maa[k[c-1].fr*1000+k[c-1].sc].end());
        }
        else{
            cin>>c>>d;
            l=0;
            r=1;
            for(i=1 ; i<=a ; i++){
                dp[i]=0;
            }
            t[0]=c;
            dp[c]=1;
            while(l<r){
                for(i=0 ; i<vas[t[l]].size() ; i++){
                    if(dp[vas[t[l]][i]]==0 && maa[vas[t[l]][i]*1000+t[l]][maa[vas[t[l]][i]*1000+t[l]].size()-1]>=d){
                        t[r]=vas[t[l]][i];
                        r++;
                        dp[vas[t[l]][i]]=1;
                    }
                }
                l++;
            }
            cout<<r<<endl;
        }
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...