Submission #1044958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1044958		vjudge1	Street Lamps (APIO19_street_lamps)	C++17	0 / 100	25 ms	44124 KiB

street_lamps

#include "bits/stdc++.h"
using namespace std;

#define int int64_t    
#define pb push_back

using lint=__int128_t;

const int lim=200100;
const int mod=1e9+7;

using pii=pair<int,int>;

pii edges[lim];

vector<pii*>v[lim];

int cnt,weg;
bool vis[lim];

void dfs(int node){
    cnt++;
    vis[node]=1;
    for(pii*p:v[node]){
        auto[f,s]=*p;
        if(!vis[f]&&weg<=s){
            dfs(f);
        }
    }
}

struct edge{
    int x,y,w;
};

int par[lim],tmm[lim];
vector<pii>sz[lim];

int find(int i){
    if(par[i]==i)return i;
    return find(par[i]);
}

void unite(int i,int j,int t){
    i=find(i),j=find(j);
    if(i!=j){
        if(sz[i].back()<sz[j].back())swap(i,j);
        //cerr<<"united "<<i<<" <-- "<<j<<"\n";
        par[j]=i;
        sz[i].pb({t,sz[i].back().second+sz[j].back().second});
        tmm[j]=t;
    }
}

int findat(int i,int t){
    if(par[i]==i||t<tmm[i])return i;
    return findat(par[i],t);
}

int findsz(int i,int t){
    i=findat(i,t);
    int l=0,r=sz[i].size()-1,ans=-1;
    while(l<=r){
        int mid=(l+r)>>1;
        if(sz[i][mid].first<=t){
            ans=sz[i][mid].second;
            l=mid+1;
        }else{
            r=mid-1;
        }
    }
    return ans;
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#ifdef Local  
    freopen(".in","r",stdin);freopen(".out","w",stdout);
#endif
    int n,m;
    cin>>n>>m;
    if(n<=1000&&m<=1000){
        for(int i=0;i<m;i++){
            int x,y,w;
            cin>>x>>y>>w;
            edges[i<<1]={y,w};
            v[x].pb(edges+(i<<1));
            edges[(i<<1)+1]={x,w};
            v[y].pb(edges+(i<<1)+1);
        }
        int Q;
        cin>>Q;
        for(int i=0;i<Q;i++){
            int t,x,y;
            cin>>t>>x>>y;
            if(t==1){
                x--;
                x<<=1;
                edges[x].second=edges[x|1].second=y;
            }else{
                cnt=0;
                weg=y;
                for(int i=0;i<=n;i++)vis[i]=0;
                dfs(x);
                cout<<cnt<<"\n";
            }
        }
        return 0;
    }else{
        edge vv[m];
        for(int i=0;i<m;i++){
            cin>>vv[i].x>>vv[i].y>>vv[i].w;
        }
        for(int i=0;i<=n;i++){
            par[i]=i;
            sz[i].pb({-mod*mod,1});
        }
        if(m){
            sort(vv,vv+m,[&](edge&e1,edge&e2) -> bool {
                return e1.w>e2.w;
            });
        }
        for(int i=0;i<m;i++){
            unite(vv[i].x,vv[i].y,-vv[i].w);
        }
        int Q;
        cin>>Q;
        for(int i=0;i<Q;i++){
            int t,x,y;
            cin>>t>>x>>y;
            assert(t==2);
            cout<<findsz(x,-y)<<"\n";
        }
        return 0;
    }
    assert(0);
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20