Submission #136777

#	Time	Username	Problem	Language	Result	Execution time	Memory
136777		KLPP	Bridges (APIO19_bridges)	C++14	29 / 100	3097 ms	16668 KiB

bridges

#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
typedef pair<lld,lld> pii;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
class ST{
  lld arr[400000];
  lld mid[400000];
public:
  void build(int a, int b, int node){
    if(a==b){
      arr[node]=0;
      return;
    }
    mid[node]=(a+b)/2;
    build(a,mid[node],2*node);
    build(mid[node]+1,b,2*node+1);
    arr[node]=min(arr[2*node],arr[2*node+1]);
    //delete(&mid);
  }
  void update(int a, int b, int node, int pos, lld val){
    if(pos<a || b<pos)return;
    if(a==b){
      arr[node]=val;
      return;
    }
    
    update(a,mid[node],2*node,pos,val);
    update(mid[node]+1,b,2*node+1,pos,val);
    arr[node]=min(arr[2*node],arr[2*node+1]);
    //delete(&mid);
  }
  lld query(int a, int b, int node, int x, int y){
    if(b<x || y<a)return 1000000000000;
    if(x<=a && b<=y)return arr[node];
    return min(query(a,mid[node],2*node,x,y),query(mid[node]+1,b,2*node+1,x,y));
  }
  
  void print(int a, int b, int node){
    cout<<a<<" "<<b<<" "<<arr[node]<<endl;
    if(a==b)return;
    int mid=(a+b)/2;
    print(a,mid,2*node);
    print(mid+1,b,2*node+1);
  }
};
class DSU{
  int parent[1000000];
  int size[1000000];
public:
  void init(int N){
    rep(i,0,N){
      parent[i]=i;
      size[i]=1;
    }
  }
  int root(int node){
    if(parent[node]==node)return node;
    parent[node]=root(parent[node]);
    return parent[node];
  }
  void merge(int a, int b){
    a=root(a);
    b=root(b);
    if(a==b)return;
    if(size[a]<size[b])swap(a,b);
    parent[b]=a;
    size[a]+=size[b];
  }
  int SZ(int node){
    return size[root(node)];
  }
  void print(){
    for(int i=0;i<10;i++)cout<<parent[i]<<endl;
  }
};
int main(){
  
  int n,m,q;
  cin>>n>>m;
  ST S;
  lld edgelist[m][3];
  rep(i,0,m){
    rep(j,0,3){
      cin>>edgelist[i][j];
      if(j<2)edgelist[i][j]--;
    }
  }
  cin>>q;
  if(m*q<=10000000){
    while(q--){
      int type;
      cin>>type;
      if(type==1){
	int num;
	lld val;
	cin>>num>>val;
	num--;
	edgelist[num][2]=val;
      }else{
	int start;
	lld w;
	cin>>start>>w;
	start--;
	vector<int> nei[n];
	bool visited[n];
	rep(i,0,n)visited[i]=false;
	//cout<<start<<endl;
	rep(i,0,m){
	  if(edgelist[i][2]>=w){
	    //cout<<edgelist[i][0]<<" "<<edgelist[i][1]<<endl;
	    nei[edgelist[i][0]].push_back(edgelist[i][1]);
	    nei[edgelist[i][1]].push_back(edgelist[i][0]);
	  }
	}
	queue<int> q;
	q.push(start);
	visited[start]=true;
	while(!q.empty()){
	  int u=q.front();q.pop();
	  trav(v,nei[u]){
	    if(!visited[v]){
	      visited[v]=true;
	      q.push(v);
	    }
	  }
	}
	lld ans=0;
	rep(i,0,n)ans+=visited[i];
	cout<<ans<<endl;
      }
    }
    return 0;
  }
  bool chain=(m==n-1);
  rep(i,0,m){
    if(edgelist[i][0]!=i || edgelist[i][1]!=i+1)chain=false;
  }
  int t,pos,start,hi,lo,mid;
  lld val,weight,ans;
  if(chain){
    S.build(0,n-2,1);
    rep(i,0,n-1){
      S.update(0,n-2,1,i,edgelist[i][2]);
    }
    while(q--){
      
      cin>>t;
      if(t==1){
	
	cin>>pos>>val;
	pos--;
	S.update(0,n-2,1,pos,val);
      }else{
	
	cin>>start>>weight;
	start--;
	ans=0;
	
	if(start>0){
	  hi=start;
	  lo=-1;
	  while(hi-lo>1){
	    int mid=(hi+lo)/2;
	    if(S.query(0,n-2,1,mid,start-1)<weight)lo=mid;
	    else hi=mid;
	  }
	  ans+=start-hi;
	}
	if(start<n-1){
	  
	  hi=n-1;
	  lo=start-1;
	  while(hi-lo>1){
	    mid=(hi+lo)/2;
	    if(S.query(0,n-2,1,start,mid)<weight)hi=mid;
	    else lo=mid;
	  }
	  ans+=lo-(start-1);
	}
	cout<<ans+1<<endl;
      }
    }
    return 0;
  }
  vector<pair<lld,pii> > V;
  rep(i,0,m){
    V.push_back(pair<lld,pii>(edgelist[i][2]+1,pii(-edgelist[i][0],-edgelist[i][1])));
  }
  lld answers[q+1];
  rep(i,0,q){
    int type;
    scanf("%d",&type);
    int start;
    lld w;
    scanf("%d %lld",&start,&w);
    start--;
    V.push_back(pair<lld,pii>(w,pii(i+1,start)));
  }
  sort(V.begin(),V.end());
  reverse(V.begin(),V.end());
  DSU *D=new DSU();
  D->init(n);
  rep(i,0,V.size()){
    if(V[i].second.first<=0){//UPD
      //cout<<"U"<<endl;
      D->merge(-V[i].second.first,-V[i].second.second);
    }else{//Q
      //out<<"Q"<<endl;
      //D->print();
      answers[V[i].second.first]=D->SZ(V[i].second.second);
    }
  }
  rep(i,1,q+1)printf("%lld\n",answers[i]);
  return 0;
}

Compilation message (stderr)

bridges.cpp: In function 'int main()':
bridges.cpp:6:33: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i,a,b) for(int i=a;i<b;i++)
bridges.cpp:206:7:
   rep(i,0,V.size()){
       ~~~~~~~~~~~~               
bridges.cpp:206:3: note: in expansion of macro 'rep'
   rep(i,0,V.size()){
   ^~~
bridges.cpp:195:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&type);
     ~~~~~^~~~~~~~~~~~
bridges.cpp:198:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %lld",&start,&w);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~

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