oj.uz

답안 #287052

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
287052 2020-08-31T10:22:57 Z crossing0ver Traffickers (RMI18_traffickers) C++17
0 / 100
 3500 ms 36256 KB 
#include<bits/stdc++.h>
#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;
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;

void add(int a,int 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].insert({k,c});
				c++;
				a = P[a][0];
			}
		//	c++;
			s[root].insert({k,c});
			c = k-1;
			while (b != root) {
				s[b].insert({k,c});
				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({k,c});
			c = k-1;
			while (b != root) {
				s[b].erase(s[b].find(make_pair(k,c)));
				c--;
				b = P[b][0];
			}
}
		
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;
		mp[{a,b}]++;
		add(a,b);
	}cin >> q;
	for (int y = 1; y <= q; y++) {
		int tp;
		cin >> tp;
		if (tp == 1) {
			int a,b; cin >> a >> b;
			mp[{a,b}]++;
			add(a,b);
		}else if (tp == 2) {
			int a,b; cin >> a >> b;
			erase(a,b);
		}else {
			vi path;
			int u,v,t1,t2;
			cin >> u >> v >> t1 >> t2;
			int root = lca(u,v);
			//cout <<root<<"E\n";
			while (u != root) {
				path.pb(u);
				u = P[u][0];
			}
			
			while (v != root) {
				path.pb(v);
				v = P[v][0];
			}
			if (root) path.pb(root);
			ll ans = 0;
			for (int i : path) {
			//	cout << i <<"s ";
		//	cout << i <<" ";
				for (auto j : s[i]) {
				//	cout << "Q "<<j.fi<<"S ";
					//cout << j.fi <<' '<< j.se <<'s';
					int k = j.fi;
					int rem = j.se;
					if (t1 + rem <= t2) {
					ans += (t2 - (t1 + rem) + k )/k;
				}
				}
			}
			cout << ans <<'\n';
			
			
		}
	}
}

Compilation message

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

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 2560 KB Output isn't correct
2 Incorrect 28 ms 2944 KB Output isn't correct
3 Incorrect 11 ms 2944 KB Output isn't correct

Subtask #2
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1012 ms 7288 KB Output isn't correct
2 Incorrect 837 ms 7188 KB Output isn't correct
3 Runtime error 1134 ms 14756 KB Execution killed with signal 11
4 Incorrect 962 ms 7288 KB Output isn't correct
5 Incorrect 863 ms 7288 KB Output isn't correct
6 Incorrect 941 ms 7416 KB Output isn't correct
7 Runtime error 237 ms 13816 KB Execution killed with signal 11
8 Incorrect 1172 ms 7416 KB Output isn't correct
9 Incorrect 3007 ms 7704 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3549 ms 35748 KB Time limit exceeded
2 Execution timed out 3591 ms 36108 KB Time limit exceeded
3 Execution timed out 3571 ms 36072 KB Time limit exceeded
4 Execution timed out 3591 ms 35120 KB Time limit exceeded
5 Execution timed out 3594 ms 34960 KB Time limit exceeded
6 Execution timed out 3595 ms 36224 KB Time limit exceeded
7 Execution timed out 3593 ms 36256 KB Time limit exceeded
8 Execution timed out 3593 ms 36024 KB Time limit exceeded