Submission #712273

#	Time	Username	Problem	Language	Result	Execution time	Memory
712273		yuseok0803	Traffickers (RMI18_traffickers)	C++14	10 / 100	2446 ms	524288 KiB

traffickers

#include <stdio.h>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <stack>
#include <ctype.h>
#define p(x,y) pair<x, y>
#define pii pair<int, int>
#define v(x) vector<x>
#define q(x) queue<x>
#define pq(x) priority_queue<x>
#define uppq(x, comp) priority_queue<x, vector<x>, comp>
#define st(x) set<x>  
#define m(x, y) map<x, y>
#define fi(s,e) for(int i=s;i<e;i++)
#define fj(s,e) for(int j=s;j<e;j++)
#define fk(s,e) for(int k=s;k<e;k++)
typedef long long int ll;
typedef unsigned long long int ull;
typedef __int128 ulll;
using namespace std;

int n,k,q;
int ordernum;
v(int) pushvec;
v(v(int)) vec;
int order[2][30010];
int par[30010][20];
ll ans[50010];
int fen[50010][20][21];

v(p(pii, pii)) pushlot;
v(v(p(pii, pii))) add;
v(v(p(pii, pii))) ask;

void up(int now, int parent){
	order[0][now]=ordernum++;
	par[now][0]=parent;
	fi(1,16) par[now][i] = par[par[now][i-1]][i-1];
	
	int sz = vec[now].size();
	fi(0,sz){
		int next = vec[now][i];
		if(next != parent) up(next, now);
	}
	order[1][now]=ordernum;
	return;
}

int find(int a, int b){
	if(order[0][a] <= order[0][b] && order[1][a] >= order[1][b]) return a;
	if(order[0][a] >= order[0][b] && order[1][a] <= order[1][b]) return b;
	
	for(int i = 15; i >= 0; i--){
		int anc = par[a][i];
		if(order[0][anc] <= order[0][b] && order[1][a] >= order[1][b]) continue;
		a = anc;
	}
	return par[a][0];
}

void make(int a, int b, int th, int pl){
	v(int) forward,backward;
	v(int) tot;
	int lca = find(a,b);
	
	while(1){
		forward.push_back(a);
		if(a==lca) break;
		
		a=par[a][0];
	}
	
	while(1){
		backward.push_back(b);
		if(b==lca) break;
		
		b=par[b][0];
	}
	
	int sza,szb,sz;
	sza = forward.size();
	szb = backward.size();
	for(int i = szb-2; i >= 0; i--) forward.push_back(backward[i]);
	
	sz = sza+szb-1;
	fi(0,sz){
		int now = forward[i];
		add[now].push_back({{th, pl},{i, sz}});
	}
	return;
}

void change(int t, int diff, int th, int sz){
	while(t <= q+1){
		fen[t][th][sz]+=diff;
		t+=(t&(-t));
	}
	return;
}

int find(int l, int r, int th, int sz){
	int ret=0;
	
	while(r>0){
		ret += fen[r][th][sz];
		r -= (r&(-r));
	}
	
	l--;
	while(l>0){
		ret -= fen[l][th][sz];
		l -= (l&(-l));
	}
	
	return ret;
}

void spreadfind(int now, int parent){
	int sz1, sz2, sz;
	sz1 = add[now].size();
	fi(0,sz1){
		p(pii, pii) pic = add[now][i];
		change(pic.first.first, pic.first.second, pic.second.first, pic.second.second);
	}
	
	sz2 = ask[now].size();
	fi(0,sz2){
		p(pii, pii) pic = ask[now][i];
		int tim = min(19, pic.second.first);
		fj(0,tim+1){
			fk(1,21){
				ans[pic.first.first] += (ll)(pic.first.second*find(1, pic.second.second, j, k)*((pic.second.first-j)/k+1));
			}
		}
	}
	
	sz = vec[now].size();
	fi(0,sz){
		int next = vec[now][i];
		if(next != parent) spreadfind(next, now);
	}
	
	fi(0,sz1){
		p(pii, pii) pic = add[now][i];
		change(pic.first.first, -pic.first.second, pic.second.first, pic.second.second);
	}
	
	return;
}

int main(void){
	scanf("%d",&n);
	fi(0,n+1) vec.push_back(pushvec);
	fi(0,n+1) add.push_back(pushlot);
	fi(0,n+1) ask.push_back(pushlot);
	
	fi(1,n){
		int a,b;
		scanf("%d%d",&a,&b);
		vec[a].push_back(b);
		vec[b].push_back(a);
	}
	
	up(1,1);
	
	scanf("%d",&k);
	fi(0,k){
		int a,b;
		scanf("%d%d",&a,&b);
		make(a,b,1,1);
	}
	
	scanf("%d",&q);
	int qcnt=0;
	fi(2,q+2){
		int t,a,b;
		scanf("%d%d%d",&t,&a,&b);
		if(t==1) make(a,b,i,1);
		else if(t==2) make(a,b,i,-1);
		else{
			int t1,t2,lca;
			scanf("%d%d",&t1,&t2);
			lca = find(a,b);
			
			if(t1){
				ask[a].push_back({{qcnt,-1},{t1-1,i}});
				ask[b].push_back({{qcnt,-1},{t1-1,i}});
				ask[lca].push_back({{qcnt,1},{t1-1,i}});
				if(lca!=1) ask[par[lca][0]].push_back({{qcnt,1},{t1-1,i}});
			}
			
			ask[a].push_back({{qcnt,1},{t2,i}});
			ask[b].push_back({{qcnt,1},{t2,i}});
			ask[lca].push_back({{qcnt,-1},{t2,i}});
			if(lca!=1) ask[par[lca][0]].push_back({{qcnt,-1},{t2,i}});
			
			qcnt++;
		}
	}
	
	spreadfind(1,-1);
	
	fi(0,qcnt) printf("%lld\n",ans[i]);
	return 0;
}

Compilation message (stderr)

traffickers.cpp: In function 'int main()':
traffickers.cpp:158:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
traffickers.cpp:165:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  165 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
traffickers.cpp:172:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |  scanf("%d",&k);
      |  ~~~~~^~~~~~~~~
traffickers.cpp:175:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  175 |   scanf("%d%d",&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~
traffickers.cpp:179:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  179 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
traffickers.cpp:183:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  183 |   scanf("%d%d%d",&t,&a,&b);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~
traffickers.cpp:188:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  188 |    scanf("%d%d",&t1,&t2);
      |    ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 15
• Subtask 2: 0 / 45
• Subtask 3: 0 / 40