제출 #587521

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
587521		penguinhacker	Jail (JOI22_jail)	C++17	60 / 100	583 ms	32336 KiB

jail

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=120000, INF=69696969, B=300;
int n, m, s[mxN], t[mxN], t2[mxN], lc[mxN], cnt[mxN];
int p[mxN], d[mxN], hd[mxN], sz[mxN], tin[mxN], timer, tin2[mxN];
vector<int> adj[mxN];

void dfs1(int u=0) {
	sz[u]=1;
	for (int& v : adj[u]) {
		adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
		p[v]=u, d[v]=d[u]+1;
		dfs1(v);
		sz[u]+=sz[v];
		if (sz[v]>sz[adj[u][0]])
			swap(adj[u][0], v);
	}
}

void dfs2(int u=0, int r=0) {
	hd[u]=r, tin[u]=timer++;
	if (adj[u].empty())
		return;
	dfs2(adj[u][0], r);
	for (int i=1; i<adj[u].size(); ++i)
		dfs2(adj[u][i], adj[u][i]);
}

int lca(int u, int v) {
	for (; hd[u]!=hd[v]; v=p[hd[v]])
		if (d[hd[u]]>d[hd[v]])
			swap(u, v);
	return d[u]<d[v]?u:v;
}

void dfs3(int u=0) {
	for (int v : adj[u])
		dfs3(v), cnt[u]+=cnt[v];
}

int init[mxN], st[1<<18], lz[1<<18];

void bld(int u=1, int l=0, int r=n-1) {
	lz[u]=0;
	if (l==r) {
		st[u]=init[l];
		return;
	}
	int mid=(l+r)/2;
	bld(2*u, l, mid);
	bld(2*u+1, mid+1, r);
	st[u]=min(st[2*u], st[2*u+1]);
}

void psh(int u, int l, int r) {
	if (lz[u]) {
		st[u]+=lz[u];
		if (l!=r)
			lz[2*u]+=lz[u], lz[2*u+1]+=lz[u];
		lz[u]=0;
	}
}

void upd(int ql, int qr, int x, int u=1, int l=0, int r=n-1) {
	psh(u, l, r);
	if (l>qr||r<ql)
		return;
	if (ql<=l&&r<=qr) {
		lz[u]=x;
		psh(u, l, r);
		return;
	}
	int mid=(l+r)/2;
	upd(ql, qr, x, 2*u, l, mid);
	upd(ql, qr, x, 2*u+1, mid+1, r);
	st[u]=min(st[2*u], st[2*u+1]);
}

int qry(int u=1, int l=0, int r=n-1) {
	psh(u, l, r);
	if (st[u]>1)
		return -1;
	if (l==r)
		return l;
	int mid=(l+r)/2;
	int x=qry(2*u, l, mid);
	return x!=-1?x:qry(2*u+1, mid+1, r);
}

void upd_path(int u, int v) {
	for (; hd[u]!=hd[v]; v=p[hd[v]]) {
		if (d[hd[u]]>d[hd[v]])
			swap(u, v);
		upd(tin[hd[v]], tin[v], -1);
	}
	if (tin[u]>tin[v])
		swap(u, v);
	upd(tin[u], tin[v], -1);
}

queue<int> q;
bool good[mxN][2];

void check(int i, int j) {
	assert(!good[i][j]);
	good[i][j]=1;
	if (good[i][0]&&good[i][1])
		q.push(i);
}

int ord[mxN], dp[mxN], highest[mxN], need[mxN];
bool active[mxN], small[mxN];
vector<int> todo[mxN];

void upd_active() {
	for (int i=0; i<n; ++i) {
		int u=ord[i];
		dp[u]=active[u];
		highest[u]=active[u]?u:(u?highest[p[u]]:-1);
		if (u)
			dp[u]+=dp[p[u]];
	}
}

int blocking(int i) {
	return dp[s[i]]+dp[t[i]]-dp[lc[i]]-(lc[i]?dp[p[lc[i]]]:0)-1;
}

void make_small(int i) {
	small[i]=1;
	need[i]=0;
	if (s[i])
		for (int u=highest[p[s[i]]]; u!=-1&&d[u]>d[lc[i]]; u=highest[p[u]])
			todo[u].push_back(i), ++need[i];
	for (int u=highest[t[i]]; u!=-1&&d[u]>d[lc[i]]; u=highest[p[u]])
		todo[u].push_back(i), ++need[i];
	if (active[lc[i]]&&lc[i]!=s[i])
		todo[lc[i]].push_back(i), ++need[i];
}

void solve() {
	cin >> n;
	for (int i=0; i<n; ++i) {
		adj[i].clear();
		active[i]=0;
		cnt[i]=0, t2[i]=-1;
		todo[i].clear();
	}
	for (int i=1; i<n; ++i) {
		int u, v;
		cin >> u >> v, --u, --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	timer=0;
	dfs1();
	dfs2();
	cin >> m;
	memset(good, 0, 2*m);
	for (int i=0; i<m; ++i) {
		cin >> s[i] >> t[i], --s[i], --t[i];
		t2[t[i]]=i;
		lc[i]=lca(s[i], t[i]);
		active[s[i]]=1;
		++cnt[s[i]], ++cnt[t[i]], --cnt[lc[i]];
		if (lc[i])
			--cnt[p[lc[i]]];
	}
	dfs3();

	queue<int>().swap(q);
	for (int i=0; i<n; ++i) {
		if (cnt[i]==1&&t2[i]!=-1)
			check(t2[i], 0);
		tin2[tin[i]]=i;
		init[tin[i]]=cnt[i]<=1?INF:cnt[i];
	}
	bld();

	iota(ord, ord+n, 0);
	sort(ord, ord+n, [](int a, int b) { return d[a]<d[b]; });
	upd_active();
	for (int i=0; i<m; ++i) {
		int x=blocking(i);
		if (x==0) {
			small[i]=1;
			check(i, 1);
		} else if (x<=B+5)
			make_small(i);
	}

	for (int rep=0; q.size(); ++rep, q.pop()) {
		int i=q.front();
		//cout << i << endl;
		upd_path(s[i], t[i]);
		while(st[1]<=1) {
			assert(st[1]==1);
			int pos=qry();
			assert(pos!=-1);
			int u=tin2[pos];
			if (t2[u]!=-1)
				check(t2[u], 0);
			upd(pos, pos, INF);
		}
		active[s[i]]=0;
		for (int j : todo[s[i]])
			if ((--need[j])==0)
				check(j, 1);
		if (rep%B==B-1) {
			upd_active();
			for (int j=0; j<m; ++j) {
				if (small[j])
					continue;
				int x=blocking(j);
				if (x<=B+5)
					make_small(j);
			}
		}
	}
	for (int i=0; i<m; ++i)
		if (!good[i][0]||!good[i][1]) {
			cout << "No\n";
			return;
		}
	cout << "Yes\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--)
		solve();
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

jail.cpp: In function 'void dfs2(int, int)':
jail.cpp:29:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for (int i=1; i<adj[u].size(); ++i)
      |                ~^~~~~~~~~~~~~~

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