Submission #617967

#	Time	Username	Problem	Language	Result	Execution time	Memory
617967		patrikpavic2	Jail (JOI22_jail)	C++17	0 / 100	3427 ms	1048576 KiB

jail

#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 (stderr)

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
• Subtask 2: 0 / 5
• Subtask 3: 0 / 16
• Subtask 4: 0 / 28
• Subtask 5: 0 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23