oj.uz

Submission #643155

# Submission time Handle Problem Language Result Execution time Memory
643155 2022-09-21T10:35:46 Z TimDee Traffickers (RMI18_traffickers) C++17
0 / 100
 291 ms 398044 KB 
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for (int i=0; i<n; ++i)
#define int long long

vector<vector<int>> adj(5001);
vector<vector<int>> cnt(5001,vector<int>(5001,0));

int path[5001];
int ptr=0;

void dfs(int u, int p, int to) {
	for (auto v:adj[u]) {
		if (v==p) continue;
		if (v==to) {
			path[ptr++]=v;
			path[ptr++]=u;
			return;
		}
		dfs(v,u,to);
		if (ptr && path[ptr-1]==v) {
			path[ptr++]=u;
			return;
		}
	}
}

void solve() {

	int n; cin>>n;
	//if (n>5000) exit(0);

	forn(i,n-1) {
		int u,v; cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	for (int i=0; i<=5000; ++i) {
		path[i]=0;
	}

	int K; cin>>K;
	forn(q,K) {
		int u,v; cin>>u>>v;
		ptr=0;
		dfs(u,0,v);
		for (int l=0, r=ptr-1; l<r; ++l, --r) {
			swap(path[l],path[r]);
		}
		for (int i=0; i<ptr; ++i) {
			for (int j=0; j*ptr+i<5000; ++j) cnt[path[i]][j*ptr+i]++;
		}
	}

	int Q; cin>>Q;
	forn(QQ,Q) {
		int q; cin>>q;
		if (q==1) {
			int u,v; cin>>u>>v;
			ptr=0;
			dfs(u,0,v);
			for (int l=0, r=ptr-1; l<r; ++l, --r) {
				swap(path[l],path[r]);
			}
			for (int i=0; i<ptr; ++i) {
				for (int j=0; j*ptr+i<5000; ++j) cnt[path[i]][j*ptr+i]++;
			}
		} else if (q==2) {
			int u,v; cin>>u>>v;
			ptr=0;
			dfs(u,0,v);
			for (int l=0, r=ptr-1; l<r; ++l, --r) {
				swap(path[l],path[r]);
			}
			for (int i=0; i<ptr; ++i) {
				for (int j=0; j*ptr+i<5000; ++j) cnt[path[i]][j*ptr+i]--;
			}
		} else {
			int u,v; cin>>u>>v;
			ptr=0;
			dfs(u,0,v);
			for (int l=0, r=ptr-1; l<r; ++l, --r) {
				swap(path[l],path[r]);
			}
			int ans=0;
			int l,r; cin>>l>>r;
			r=min(r,n);
			for (int i=0; i<ptr; ++i) {
				for (int j=l; j<=r; ++j) ans+=cnt[path[i]][j];
			}
			cout<<ans<<'\n';
		}

	}

}

int32_t main() {
	solve();
	return 0;
}

Subtask #1
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 79 ms 196440 KB Output isn't correct
2 Incorrect 114 ms 196456 KB Output isn't correct
3 Incorrect 105 ms 196312 KB Output isn't correct

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Runtime error 258 ms 397944 KB Execution killed with signal 11
2 Runtime error 243 ms 397916 KB Execution killed with signal 11
3 Runtime error 291 ms 397980 KB Execution killed with signal 11
4 Runtime error 237 ms 397880 KB Execution killed with signal 11
5 Runtime error 256 ms 397900 KB Execution killed with signal 11
6 Runtime error 235 ms 397880 KB Execution killed with signal 11
7 Runtime error 241 ms 397952 KB Execution killed with signal 11
8 Runtime error 238 ms 398016 KB Execution killed with signal 11
9 Runtime error 249 ms 397960 KB Execution killed with signal 11

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 239 ms 397952 KB Execution killed with signal 11
2 Runtime error 289 ms 397968 KB Execution killed with signal 11
3 Runtime error 240 ms 397988 KB Execution killed with signal 11
4 Runtime error 241 ms 397868 KB Execution killed with signal 11
5 Runtime error 239 ms 397856 KB Execution killed with signal 11
6 Runtime error 272 ms 397928 KB Execution killed with signal 11
7 Runtime error 234 ms 397932 KB Execution killed with signal 11
8 Runtime error 281 ms 398044 KB Execution killed with signal 11