oj.uz

Submission #653158

# Submission time Handle Problem Language Result Execution time Memory
653158 2022-10-25T21:57:10 Z inksamurai Inside information (BOI21_servers) C++17
2.5 / 100
 136 ms 5732 KB 
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3D2ZDxo ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}

template<class E>
struct treelca{
	int n;
	int timer=0;
	vec(vec(E)) adj;
	vi tin,tout,tour,tourid;
	vi segtree;
	vi depth;
	treelca(int m,int root,vec(vec(E)) neadj){
		init(m,root,neadj);
	}
	void init(int m,int root,vec(vec(E)) neadj){
		n=m;
		tin.clear();
		tout.clear();
		tour.clear();
		tourid.clear();
		depth.clear();
		tin.resize(n,0);
		tout.resize(n,0);
		tourid.resize(n,0);
		depth.resize(n,0);
		adj=neadj;
		dfs(root,-1);
		segtree.resize(4*sz(tour));
		build(1,0,sz(tour)-1);
	}
	void dfs(int v,int par){
		tour.pb(v);
		tourid[v]=sz(tour)-1;
		tin[v]=timer++;
		for(auto e:adj[v]){
			int u=e.to;
			if(u==par) continue;
			depth[u]=depth[v]+1;
			dfs(u,v);
			tour.pb(v);
		}
		tout[v]=timer++;
	}
	void build(int node,int l,int r){
		if(l==r){
			segtree[node]=tour[l];
		}else{
			int m=(l+r)>>1;
			build(node*2,l,m);
			build(node*2+1,m+1,r);
			segtree[node]=(tin[segtree[node*2]]<tin[segtree[node*2+1]]?segtree[node*2]:segtree[node*2+1]);
		}
	}
	int query(int node,int l,int r,int _l,int _r){
		if(l>_r or r<_l) return -1;
		if(l>=_l and r<=_r) return segtree[node];
		int m=(l+r)>>1;
		int vl=query(node*2,l,m,_l,_r);
		int vr=query(node*2+1,m+1,r,_l,_r);
		if(min(vl,vr)==-1) return max(vl,vr);
		return (tin[vl]<tin[vr]?vl:vr);
	}
	int ancestor(int from,int to){
		int tinfrom=tin[from],tinto=tin[to];
		if(tinfrom>tinto) swap(tinfrom,tinto);
		return query(1,0,sz(tour)-1,tinfrom,tinto);
	}
	int dist(int u,int v){
		return depth[u]+depth[v]-depth[ancestor(u,v)]*2;
	}
};

struct E{
	int to,w;
	E(int _to=0,int _w=0):
	to(_to),w(_w){}
};

const int inf=1e9;

signed main(){
_3D2ZDxo;
	int n,q;
	cin>>n>>q;
	assert(n<=4000);
	q+=n-1;
	vec(vec(E)) adj(n);
	vec(vec(pii)) qry(n);
	vi pns(q,-1);
	rep(i,q){
		char ch;
		cin>>ch;
		if(ch=='S'){
			int u,v;
			cin>>u>>v;
			u-=1,v-=1;
			adj[u].pb(E(v,i));
			adj[v].pb(E(u,i));
		}else if(ch=='Q'){
			int u,v;
			cin>>u>>v;
			u-=1,v-=1;
			qry[v].pb({u,i});
		}else{
			int v;
			cin>>v;
			v-=1;
			pns[i]=inf;
		}
	}
	vi leb(n); // last node where increasing seq broke
	vi bel(n); // last node where decreasing seq broke
	vi par(n);
	vi par_wit(n);
	auto dfs=[&](auto self,int v,int _lst)->void{
		for(auto [u,w]:adj[v]){
			if(u==par[v]) continue;
			if(_lst>w){
				leb[u]=v;
			}else{
				leb[u]=leb[v];
			}
			if(_lst<w){
				bel[u]=v;
			}else{
				bel[u]=bel[v];
			}
			par[u]=v;
			par_wit[u]=w;
			self(self,u,w);
		}
	};
	dfs(dfs,0,0);
	vec(vi) afup(20,vi(n)); // affine up
	afup[0]=par;
	rng(j,1,20){
		rep(v,n){
			int up=afup[j-1][v];
			afup[j][v]=afup[j-1][up];
		}
	}
	treelca<E> lca(n,0,adj);
	auto move_down=[&](int v,int up)->int{
		int dist=lca.dist(v,up)-1;
		per(j,20){
			if(dist>>j&1){
				v=afup[j][v];
			}
		}
		return v;
	};
	// rep(v,n){
	// 	for(auto p:qry[v]){
	// 		int u=p.fi;
	// 		int j=p.se;
	// 		bool pok=0;
	// 		if(u==v){
	// 			pok=1;
	// 		}else{
	// 			int up=lca.ancestor(u,v);
	// 			if(up==v){
	// 				if(lca.depth[leb[u]]<=up){
	// 					pok=par_wit[u]<=j;
	// 				}
	// 			}else if(up==u){
	// 				// if(v==4) print(move_down(v,u),bel[u]);
	// 				if(lca.depth[bel[v]]<=up){
	// 					pok=par_wit[move_down(v,u)]<=j;
	// 				}
	// 			}else{
	// 				if(lca.depth[leb[u]]<=up and lca.depth[bel[v]]<=up){
	// 					int lov=move_down(v,up);
	// 					int lou=move_down(u,up);
	// 					pok=par_wit[lov]<=par_wit[lou] and par_wit[u]<=j;
	// 				}
	// 			}
	// 		}
	// 		pns[j]=pok;
	// 	}
	// }
	rep(s,n){
		vi usd(n,inf);
		usd[s]=0;
		queue<int> que;
		que.push(s);
		while(sz(que)){
			int v=que.front();
			que.pop();
			for(auto [to,w]:adj[v]){
				if(usd[to]==inf and w>=usd[v]){
					usd[to]=w;
					que.push(to);
				}
			}
		}
		for(auto p:qry[s]){
			pns[p.se]=(usd[p.fi]<=p.se);
		}
	}
	rep(i,q){
		if(pns[i]==-1) continue;
		if(pns[i]!=inf){
			cout<<(pns[i]?"yes":"no")<<"\n";
		}else{
			cout<<"0\n";
		}
	}
}

Compilation message

servers.cpp: In function 'int main()':
servers.cpp:158:7: warning: variable 'move_down' set but not used [-Wunused-but-set-variable]
  158 |  auto move_down=[&](int v,int up)->int{
      |       ^~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2644 KB Output is correct
2 Correct 38 ms 4132 KB Output is correct
3 Correct 47 ms 4324 KB Output is correct
4 Correct 36 ms 5616 KB Output is correct
5 Correct 37 ms 5732 KB Output is correct
6 Correct 119 ms 5716 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2644 KB Output is correct
2 Correct 38 ms 4132 KB Output is correct
3 Correct 47 ms 4324 KB Output is correct
4 Correct 36 ms 5616 KB Output is correct
5 Correct 37 ms 5732 KB Output is correct
6 Correct 119 ms 5716 KB Output is correct
7 Incorrect 21 ms 3372 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2644 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2644 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2712 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 2712 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2624 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 2624 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2644 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 20 ms 2644 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2644 KB Output is correct
2 Correct 53 ms 4148 KB Output is correct
3 Correct 49 ms 4280 KB Output is correct
4 Correct 47 ms 5636 KB Output is correct
5 Correct 36 ms 5688 KB Output is correct
6 Correct 136 ms 5704 KB Output is correct
7 Correct 21 ms 3548 KB Output is correct
8 Runtime error 1 ms 468 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 21 ms 2644 KB Output is correct
2 Correct 53 ms 4148 KB Output is correct
3 Correct 49 ms 4280 KB Output is correct
4 Correct 47 ms 5636 KB Output is correct
5 Correct 36 ms 5688 KB Output is correct
6 Correct 136 ms 5704 KB Output is correct
7 Correct 21 ms 3548 KB Output is correct
8 Runtime error 1 ms 468 KB Execution killed with signal 6
9 Halted 0 ms 0 KB -