oj.uz

답안 #287101

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287101 2020-08-31T11:50:04 Z crossing0ver Traffickers (RMI18_traffickers) C++17
60 / 100
 2126 ms 59408 KB 
#include<bits/stdc++.h>
//#define int long long 
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define vi vector<int>
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
const int N = 3e4+5,MXN = 2*N;
vi adj[N];
int n,k,q,tin[N],tout[N],timer,P[N][18],h[N];

void dfs(int v,int p) {
	P[v][0] = p;
	h[v] = h[p] + 1;
	tin[v] = ++timer;
	for (int h = 1; h < 18; h++)
	P[v][h] = P[ P[v][h-1] ][h-1];
	for (int i : adj[v]) {
		if (i != p)	
			dfs(i,v);
	}
	tout[v] = ++timer;
}
bool isp(int a,int b) {
	return tin[a] <= tin[b] && tout[a] >= tout[b];
}
int lca(int a,int b) {
	if (isp(a,b)) return a;
	if (isp(b,a)) return b;
	for (int h = 17; h >= 0; h--)
		if (!isp(P[a][h],b))	
				a = P[a][h];
	return P[a][0];
}

multiset<pii> s[N];
map<pii,int> mp;
int bit[21][21][N],sum[21][21][N];
void add(int k,int rem,int pos,int val) {
	for (;pos < MXN; pos += pos&-pos)
		bit[k][rem][pos]+=val;
}
int get(int k,int rem,int pos ) {
	int s = 0;
	for (;pos;pos-=pos&-pos)
		s += bit[k][rem][pos];
	return s;
}
void add(int a,int b,int val) {
	int c = 0;
	int root = lca(a,b);
	int k = h[a] - h[root] + h[b] - h[root] + 1;	
	while (a != root) {
		add(k,c,tin[a],val);
		add(k,c,tout[a],-val);
		sum[k][c][a] += val;
		c++;
		a = P[a][0];
	}
	add(k,c,tin[root],val);
	add(k,c,tout[root],-val);
	sum[k][c][root] += val;
	c = k-1;
			while (b != root) {	
			sum[k][c][b] += val;
			add(k,c,tin[b],val);
			add(k,c,tout[b],-val);												
				c--;															
				b = P[b][0];															
			}																				
}																				
void erase(int a,int b) {														
	mp[{a,b}]--;																
	if (mp[{a,b}] == 0) mp.erase({a,b});										
																				
	int root = lca(a,b);														
			int k = h[a] - h[root] + h[b] - h[root] + 1;							
			int c = 0;															
			while (a != root) {														
				s[a].erase(s[a].find(make_pair(k,c)));							
				c++;															
				a = P[a][0];														
			}																	
		//	c++;																	
			s[root].erase(s[root].find({k,c}));												
			c = k-1;															
			while (b != root) {													
				s[b].erase(s[b].find(make_pair(k,c)));							
				c--;															
				b = P[b][0];													
			}																	
}	
int get(int k,int rem,int l,int r) {
	return get(k,rem,r) - get(k,rem,l-1);
}			
																				
main() {																		
	ios::sync_with_stdio(0);													
	cin.tie(0);				
	tout[0] = 1000000000;														
	cin >> n;
	for (int i = 1 ; i < n; i++) {
		int a,b;
		cin >> a >> b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	dfs(1,0);
	cin >> k;
	for (int i = 1; i <= k; i++) {
		int a,b;
		cin >> a >> b;
		add(a,b,1);
	}cin >> q;
	for (int y = 1; y <= q; y++) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int a,b; cin >> a >> b;
			add(a,b,1);
		}else if (tp == 2) {
			int a,b; cin >> a >> b;
			add(a,b,-1);
		}else {
			vi path;
			int u,v,t1,t2;
			cin >> u >> v >> t1 >> t2;
			int root = lca(u,v);
			ll ans = 0;
			for (int k = 1; k <= 20; k++)
			for (int rem = 0; rem < k; rem++)
			{
				int e = get(k,rem,tin[root],tin[u]);
				e += get(k,rem,tin[root],tin[v]);
				e -= sum[k][rem][root];
				int b1 = t1;
					if ((b1%k) < rem) {
						b1 = b1 - (b1%k) + rem;
					}
					else 
					if ((b1%k) > rem)b1 = b1- (b1%k) + rem + k;
					if (b1 <= t2) {
					ans += (ll)e*((t2 - b1 + k )/k);
			}
		}
			cout << ans <<'\n';continue;
		}
		}
}

Compilation message

traffickers.cpp:100:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  100 | main() {
      |      ^

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 8704 KB Output is correct
2 Correct 11 ms 10112 KB Output is correct
3 Correct 14 ms 9728 KB Output is correct

Subtask #2
45.0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 189 ms 30076 KB Output is correct
2 Correct 181 ms 27384 KB Output is correct
3 Correct 186 ms 31172 KB Output is correct
4 Correct 196 ms 29716 KB Output is correct
5 Correct 190 ms 28920 KB Output is correct
6 Correct 191 ms 29352 KB Output is correct
7 Correct 186 ms 29560 KB Output is correct
8 Correct 172 ms 31712 KB Output is correct
9 Correct 119 ms 31992 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1964 ms 55576 KB Output isn't correct
2 Incorrect 2094 ms 58764 KB Output isn't correct
3 Incorrect 1836 ms 59068 KB Output isn't correct
4 Incorrect 1975 ms 47096 KB Output isn't correct
5 Incorrect 2126 ms 45000 KB Output isn't correct
6 Incorrect 1925 ms 58168 KB Output isn't correct
7 Incorrect 1307 ms 59408 KB Output isn't correct
8 Incorrect 1254 ms 59144 KB Output isn't correct