Submission #930197

#	Time	Username	Problem	Language	Result	Execution time	Memory
930197		asdf1234coding	Jail (JOI22_jail)	C++14	100 / 100	928 ms	137180 KiB

jail

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

// #define int long long
#define vi vector<int>
#define ff first
#define ss second
#define pii pair<int, int>
#define pb push_back

const int MX = 120000+10;
const int MN = 30;
int n;

vi vis; // 1 is on stack, 2 is visited
int ok=1;

vector<vi> adj2;


struct Segtree {
	void add(int u, int v) {
		adj2[u].pb(v);
		// cout<<"edge "<<u<<"->"<<v<<endl;
	}
	void build(int t=1, int l=1, int r=n) {
		if(l==r) {
			// do something with an edge
			// gotta connect ID or something
			return;
		}
		int m=(l+r)>>1;
		build(t<<1, l, m); build(t<<1|1, m+1, r);
		add(t, t<<1); add(t, t<<1|1); //add(t<<1, t); add(t<<1|1, t);
	}
	void upd(int ul, int ur, int src, int t=1, int l=1, int r=n) {
		// cout<<"upd "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
		if(ul>r || ur<l) return;
		// add edges from src to [ul, ur]
		if(ul<=l && r<=ur) {
			// do something
			add(src, t);
			return;
		}
		int m=(l+r)>>1;
		if(ul<=m) upd(ul, ur, src, t<<1, l, m);
		if(m+1<=ur) upd(ul, ur, src, t<<1|1, m+1, r);
	}
	void upd2(int ul, int ur, int src, int t=1, int l=1, int r=n) {
		// cout<<"upd2 "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
		if(ul>r || ur<l) return;
		// add edges from src to [ul, ur]
		if(ul<=l && r<=ur) {
			// do something
			add(t, src);
			return;
		}
		int m=(l+r)>>1;
		if(ul<=m) upd2(ul, ur, src, t<<1, l, m);
		if(m+1<=ur) upd2(ul, ur, src, t<<1|1, m+1, r);
	}


};


struct Segtree2 {
	void add(int u, int v) {
		adj2[u].pb(v);
		// cout<<"edge "<<u<<"->"<<v<<endl;
	}
	void build(int t=1, int l=1, int r=n) {
		if(l==r) {
			// do something with an edge
			// gotta connect ID or something
			return;
		}
		int m=(l+r)>>1;
		build(t<<1, l, m); build(t<<1|1, m+1, r);
		add((t<<1)+7*n+10, (t)+7*n+10); add((t<<1|1)+7*n+10, (t)+7*n+10); //add(t<<1, t); add(t<<1|1, t);
		// add(t+4*n+10, (t<<1)+4*n+10); add(t+4*n+10, (t<<1|1)+4*n+10); //add(t<<1, t); add(t<<1|1, t);
	}
	void upd(int ul, int ur, int src, int t=1, int l=1, int r=n) {
		// cout<<"upd "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
		if(ul>r || ur<l) return;
		// add edges from src to [ul, ur]
		if(ul<=l && r<=ur) {
			// do something
			add(src, t+7*n+10);
			return;
		}
		int m=(l+r)>>1;
		if(ul<=m) upd(ul, ur, src, t<<1, l, m);
		if(m+1<=ur) upd(ul, ur, src, t<<1|1, m+1, r);
	}
	void upd2(int ul, int ur, int src, int t=1, int l=1, int r=n) {
		// cout<<"upd2 "<<ul<<' '<<ur<<' '<<src<<' '<<t<<' '<<l<<' '<<r<<endl;
		if(ul>r || ur<l) return;
		// add edges from src to [ul, ur]
		if(ul<=l && r<=ur) {
			// do something
			add(t+7*n+10, src);
			return;
		}
		int m=(l+r)>>1;
		if(ul<=m) upd2(ul, ur, src, t<<1, l, m);
		if(m+1<=ur) upd2(ul, ur, src, t<<1|1, m+1, r);
	}

};

void chk(int cur, int par) {
	// cout<<"chk at "<<cur<<endl;
	vis[cur]=1;
	for(auto x:adj2[cur]) {
		// cout<<cur<<"->"<<x<<endl;
		if(x==par) continue;
		if(vis[x]==1) {
			ok=0; return;
		}
		if(vis[x]==0) chk(x, cur);
	}
	vis[cur]=2;
}

vi adj[MX];
// int sz[MX]; int tp[MX]; int id[MX]; int p[MX]; int dep[MX]; int di[MX];
vi sz, tp, id, p, dep, di;
vi tin, tout;
vector<vi> succ;
int tt;
int ttin=0;
void dfs1(int cur, int par) {
	tin[cur]=++ttin;
	p[cur]=par; sz[cur]=1;
	dep[cur]=dep[par]+1;
	succ[0][cur]=par;
	for(auto x:adj[cur]) {
		if(x==par) continue;
		dfs1(x, cur);
		sz[cur]+=sz[x];
	}
	tout[cur]=ttin;
}
void dfs2(int cur, int par, int top) {
	id[cur]=++tt;
	// if(id[cur]<=10) {
	// 	cout<<"at "<<cur<<' '<<tt<<endl;
	// }
	di[id[cur]]=cur;
	tp[cur]=top;
	int mxs=-1; int mxi=-1;
	for(auto x:adj[cur]) {
		if(x==par) continue;
		if(sz[x]>mxs) {
			mxs=sz[x]; mxi=x;
		}
	}
	if(mxi==-1) return;
	dfs2(mxi, cur, top);
	for(auto x:adj[cur]) {
		if(x==par||x==mxi) continue;
		dfs2(x, cur, x);
	}
}

vector<pii> getpath(int l, int r) {
	vector<pii> a,b;
	while(tp[l]!=tp[r]) {
		// cout<<l<<' '<<r<<endl;
		if(dep[tp[l] ]>dep[tp[r]]) {
			a.pb({id[tp[l]], id[l]});
			l=p[tp[l]];
		} else {
			b.pb({id[tp[r]], id[r]});
			r=p[tp[r]];
		}
	}
	// cout<<l<<' '<<r<<endl;

	a.pb({id[l], id[r]});
	reverse(b.begin(), b.end());
	for(auto x:b) a.pb(x);
	return a;
}

int blift(int x, int d) {
	// cout<<"lift node "<<x<<' '<<d<<endl;
	for(int i=MN-1; i>=0; i--) {
		if((d>>i)&1) {
			x=succ[i][x];
		}
	}
	return x;
}

pii trim(int x, int y) { // return path from x to y without y
	// x is ancestor of y
	if(tin[x]<=tin[y] && tout[y]<=tout[x]) {
		return {x, p[y]};
	}
	// y is ancestor of x
	if(tin[y]<=tin[x] && tout[x]<=tout[y]) {
		// cout<<"this case"<<endl;
		return {x, blift(x, dep[x]-dep[y]-1)};
	}
	return {x, p[y]};
}


void solve() {
	tt=0; ttin=0; ok=1;
	// cout<<"====="<<endl;
	cin>>n;
	adj2=vector<vi>(20*n);
	Segtree st; st.build();
	Segtree2 st2; st2.build();
// 	return;
	sz=vi(n+5); tp=vi(n+5); id=vi(n+5); p=vi(n+5); dep=vi(n+5); di=vi(n+5); tin=vi(n+5); tout=vi(n+5); 
	vis=vi(20*n+5);
	// cout<<"MN n+5  " <<MN<<' '<<n+5<<endl;
	succ=vector<vi>(MN, vi(n+5));
	// cout<<"???"<<endl;
	vector<pii> edges;
	for(int i=0; i<=n; i++) {
		adj[i].clear();
	}

	for(int i=0; i<n-1; i++) {
		int u,v; cin>>u>>v; adj[u].pb(v); adj[v].pb(u);
	}
	dfs1(1, 0); dfs2(1, 0, 1);
	for(int j=1; j<MN; j++) {
		for(int i=1; i<=n; i++) {
			succ[j][i]=succ[j-1][succ[j-1][i]];
		}
	}

	// for(int i=1; i<=n; i++) {
	// 	cout<<i<<": "<<id[i]<<' '<<tp[i]<<endl;
	// }
	int q; cin>>q;
	edges.pb({-1, -1});
	// return;
	for(int i=1; i<=q; i++) {
		// cout<<"qry number "<<i<<endl;
		int x,y; cin>>x>>y; edges.pb({x,y});
		// add edge from 3*n + i to [x, y]
		// trim [x, y] so that it doesnt contain y?
		auto [nx, ny] = trim(x,y);
		auto [ny2, nx2] = trim(y, x);
		// int nx=x; int ny=y;
		// cout<<"nxny "<<nx<<' '<<ny<<endl;
		vector<pii> res = getpath(nx, ny);
		vector<pii> res2 = getpath(nx2, ny2);

		for(auto seg:res) {
			// cout<<"seg "<<seg.ff<<' '<<seg.ss<<endl;
			st.upd(min(seg.ff, seg.ss), max(seg.ff, seg.ss), 4*n+i);
		}
		for(auto seg:res2) {
			st2.upd2(min(seg.ff, seg.ss), max(seg.ff, seg.ss), 4*n+i);
		}
	}
	// now in theory we have a graph where 3*n+i -> [segment s_i to t_i]
	// now gotta connect id[x] to 3*n+x and make sure no cycles


	// cout<<"almost finished building graph"<<endl;

	for(int i=1; i<=q; i++) {
		st.upd2(id[edges[i].ss], id[edges[i].ss], 4*n+i);
		st2.upd(id[edges[i].ff], id[edges[i].ff], 4*n+i);
	}

	// now dfs to find cycles
	for(int i=1; i<=q; i++) {
		if(vis[4*n+i]==0) {
			// cout<<"lol "<<3*n+i<<endl;
			chk(4*n+i, 0); 
		}
	}
	if(ok) {
		cout<<"Yes"<<endl;
	} else {
		cout<<"No"<<endl;
	}
}

int32_t main() {
	int t; cin>>t; while(t--) solve();
}

Compilation message (stderr)

jail.cpp: In function 'void solve()':
jail.cpp:250:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  250 |   auto [nx, ny] = trim(x,y);
      |        ^
jail.cpp:251:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  251 |   auto [ny2, nx2] = trim(y, x);
      |        ^

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