Submission #617960

#	Time	Username	Problem	Language	Result	Execution time	Memory
617960		patrikpavic2	Jail (JOI22_jail)	C++17	61 / 100	5106 ms	508384 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];
vector < int > put;

bool dfs(int x, int lst, int zav){
	if(x == zav){
		put.PB(x); return 1;
	}
	for(int y : v[x]){
		if(y == lst) continue;
		if(dfs(y, x, zav)){
			put.PB(x);
			return 1;
		}
	}
	return 0;
}

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);
	}
	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++){
		put.clear();
		dfs(st[i], st[i], en[i]);
		for(int j = 0;j + 1 < (int)put.size();j++){
			sm[2 * N + i].PB(put[j]);
			sm[N + put[j + 1]].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:46:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   46 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
jail.cpp:48:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~
jail.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
jail.cpp:54:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   int a, b; scanf("%d%d", &a, &b);
      |             ~~~~~^~~~~~~~~~~~~~~~
jail.cpp: In function 'int main()':
jail.cpp:82:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  int T; scanf("%d", &T);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 5 / 5
• Subtask 3: 16 / 16
• Subtask 4: 28 / 28
• Subtask 5: 12 / 12
• Subtask 6: 0 / 11
• Subtask 7: 0 / 23