oj.uz

Submission #617967

# Submission time Handle Problem Language Result Execution time Memory
617967 2022-08-01T18:17:21 Z patrikpavic2 Jail (JOI22_jail) C++17
0 / 100
 3427 ms 1048576 KB 
#include <cstdio>
#include <vector>
#include <algorithm>

#define X first
#define Y second
#define PB push_back

using namespace std;

const int N = 120500;
const int LOG = 17;

vector < int > v[N], poc[N], zav[N], sm[3 * N];
int n, q, st[N], en[N], bio[3 * N], dep[N], par[N];
vector < int > put;

void dfs(int x, int lst){
	dep[x] = dep[lst] + 1;
	par[x] = lst;
	for(int y : v[x])
		if(y != lst) dfs(y, x);
}

void napravi_put(int a, int b){
	vector < int > L, R;
	//printf("%d -> %d\n", a, b);
	while(a != b){
		if(dep[a] > dep[b])
			L.PB(a), a = par[a];
		else
			R.PB(b), b = par[b];
	}
	if((int)L.size() == 0)
		L.PB(a);
	else if((int)R.size() == 0)
		R.PB(a);
	reverse(R.begin(), R.end());
	put.clear();
	for(int x : L) put.PB(x);
	for(int x : R) put.PB(x);
}

int naso = 0;

void ciklus(int x){
	if(bio[x] == 1) { naso = 1; }
	if(bio[x]) return;
	bio[x] = 1;
	for(int y : sm[x]){
	//	printf("(%d %d) -> (%d %d) %d\n", x % N, x / N, y % N, y / N, naso);
		ciklus(y);
	}
	bio[x] = 2;
}

void solve(){
	scanf("%d", &n);
	for(int i = 1;i < n;i++){
		int a, b; scanf("%d%d", &a, &b);
		v[a].PB(b);
		v[b].PB(a);
	}
	dfs(1, 1);
	scanf("%d", &q);
	for(int i = 0;i < q;i++){
		int a, b; scanf("%d%d", &a, &b);
		st[i] = a; en[i] = b;
		poc[a].PB(i); zav[b].PB(i);
	}
	for(int i = 1;i <= n;i++){
		for(int x : poc[i])
			sm[i].PB(2 * N + x);
		for(int x : zav[i])
			sm[2 * N + x].PB(i + N);
	}
	for(int i = 0;i < q;i++){
		napravi_put(st[i], en[i]);
		for(int j = 0;j + 1 < (int)put.size();j++){
			sm[2 * N + i].PB(put[j + 1]);
			sm[N + put[j]].PB(2 * N + i);
		}
	}
	naso = 0;
	for(int i = 1;i <= n;i++) ciklus(i), ciklus(i + N);
	for(int j = 0;j < q;j++) ciklus(2 * N + j);
	printf(naso ? "No\n" : "Yes\n");
	for(int i = 1;i <= n;i++) v[i].clear(), poc[i].clear(), zav[i].clear();
	for(int i = 1;i <= n;i++) sm[i].clear(), sm[i + N].clear(), bio[i] = 0, bio[i + N] = 0;
	for(int j = 0;j < q;j++) sm[2 * N + j].clear(), bio[2 * N + j] = 0;
}

int main(){
	int T; scanf("%d", &T);
	for(;T--;) solve();
	return 0;
}

Compilation message

jail.cpp: In function 'void solve()':
jail.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
jail.cpp:60:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
jail.cpp:67:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:94:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  int T; scanf("%d", &T);
      |         ~~~~~^~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17236 KB Output is correct
2 Correct 9 ms 17264 KB Output is correct
3 Correct 9 ms 17236 KB Output is correct
4 Correct 20 ms 17296 KB Output is correct
5 Correct 34 ms 17236 KB Output is correct
6 Correct 11 ms 17236 KB Output is correct
7 Correct 10 ms 17348 KB Output is correct
8 Correct 12 ms 17564 KB Output is correct
9 Correct 314 ms 45444 KB Output is correct
10 Correct 2185 ms 507744 KB Output is correct
11 Correct 16 ms 17236 KB Output is correct
12 Correct 65 ms 17436 KB Output is correct
13 Correct 299 ms 108404 KB Output is correct
14 Correct 374 ms 141312 KB Output is correct
15 Runtime error 3427 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17236 KB Output is correct
2 Correct 12 ms 17276 KB Output is correct
3 Correct 11 ms 17364 KB Output is correct
4 Incorrect 10 ms 17236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17236 KB Output is correct
2 Correct 12 ms 17276 KB Output is correct
3 Correct 11 ms 17364 KB Output is correct
4 Incorrect 10 ms 17236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17236 KB Output is correct
2 Correct 12 ms 17276 KB Output is correct
3 Correct 11 ms 17364 KB Output is correct
4 Incorrect 10 ms 17236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 17236 KB Output is correct
2 Correct 12 ms 17276 KB Output is correct
3 Correct 11 ms 17364 KB Output is correct
4 Incorrect 10 ms 17236 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17236 KB Output is correct
2 Correct 9 ms 17236 KB Output is correct
3 Correct 13 ms 17260 KB Output is correct
4 Correct 9 ms 17236 KB Output is correct
5 Correct 16 ms 17364 KB Output is correct
6 Incorrect 12 ms 17324 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 17236 KB Output is correct
2 Correct 9 ms 17264 KB Output is correct
3 Correct 9 ms 17236 KB Output is correct
4 Correct 20 ms 17296 KB Output is correct
5 Correct 34 ms 17236 KB Output is correct
6 Correct 11 ms 17236 KB Output is correct
7 Correct 10 ms 17348 KB Output is correct
8 Correct 12 ms 17564 KB Output is correct
9 Correct 314 ms 45444 KB Output is correct
10 Correct 2185 ms 507744 KB Output is correct
11 Correct 16 ms 17236 KB Output is correct
12 Correct 65 ms 17436 KB Output is correct
13 Correct 299 ms 108404 KB Output is correct
14 Correct 374 ms 141312 KB Output is correct
15 Runtime error 3427 ms 1048576 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -