oj.uz

Submission #654112

# Submission time Handle Problem Language Result Execution time Memory
654112 2022-10-30T02:43:12 Z kym Inside information (BOI21_servers) C++14
50 / 100
 374 ms 112568 KB 
#include <bits/stdc++.h>
using namespace std;
#define int ll 
#define FOR(i,s,e) for(ll i = s; i <= (ll)e; ++i)
#define DEC(i,s,e) for(ll i = s; i >= (ll)e; --i)
#define IAMSPEED ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
#define db(x) cerr << #x << "=" << x << "\n"
#define db2(x, y) cerr << #x << "=" << x << " , " << #y << "=" << y << "\n"
#define db3(a,b,c) cerr<<#a<<"="<<a<<","<<#b<<"="<<b<<","<<#c<<"="<<c<<"\n"
#define dbv(v) cerr << #v << ":"; for (auto ite : v) cerr << ite << ' '; cerr <<"\n"
#define dbvp(v) cerr << #v << ":"; for (auto ite : v) cerr << "{"  << ite.f << ',' << ite.s << "} "; cerr << "\n"
#define dba(a,ss,ee) cerr << #a << ":"; FOR(ite,ss,ee) cerr << a[ite] << ' '; cerr << "\n"
#else
#define db(x)
#define db2(x,y)
#define db3(a,b,c)
#define dbv(v)
#define dbvp(v)
#define dba(a,ss,ee)
#endif
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long 
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(), (x).end()
#define f first 	
#define s second
#define g0(x) get<0>(x)
#define g1(x) get<1>(x)
#define g2(x) get<2>(x)
#define g3(x) get<3>(x)
#define reach cerr << "LINE: " << __LINE__ << "\n";
typedef pair <ll, ll> pi;
typedef tuple<ll,ll,ll> ti3;
typedef tuple<ll,ll,ll,ll> ti4;
ll rand(ll a, ll b) { return a + rng() % (b-a+1); }
const int MOD = 1e9 + 7;
const int inf = (int)1e9 + 500;
const long long oo = (ll)1e18 + 500;
template <typename T> bool chmax(T& a, const T b) { return a<b ? a = b, 1 : 0; }
template <typename T> bool chmin(T& a, const T b) { return a>b ? a = b, 1 : 0; }
const int MAXN = 120005;
int n;
int k;
vector<pi> V[MAXN];
vector<ti3> queries;
int twok[MAXN][20];
bool inc[MAXN][20];
bool decr[MAXN][20];
int depth[MAXN];
int W[MAXN];
int lst[MAXN][20];
int dp[MAXN];
int out[MAXN];
int st[MAXN], en[MAXN];
int cnt=1;
void predfs(int x, int p, int lvl, int w) {
	depth[x]=lvl;
	twok[x][0]=p;
	lst[x][0]=w;
	inc[x][0]=1;
	decr[x][0]=1;
	FOR(i,1,19) {
		if(twok[x][i-1]==-1)break;
		twok[x][i]=twok[twok[x][i-1]][i-1];
		lst[x][i]=lst[twok[x][i-1]][i-1];
		inc[x][i]=(inc[twok[x][i-1]][i-1]) & (inc[x][i-1]) & ((twok[x][i-1]!=1)?(lst[x][i-1] < W[ twok[x][i-1]]):1);
		decr[x][i]=(decr[twok[x][i-1]][i-1]) & (decr[x][i-1]) & ((twok[x][i-1]!=1)?(lst[x][i-1] > W[ twok[x][i-1]]):1);
	}
	for(auto v:V[x])if(v.f!=p) {
		W[v.f]=v.s;
		predfs(v.f,x,lvl+1,v.s);
	}
	
}
 
int kth_parent(int x, int k){
    for (int i = 0; i <= 19; i++){
        if (k & (1 << i)) x = twok[x][i];
        if (x <= -1) return -1;
    }
    return x;
}
int prex=0, prey=inf;
bool checkinc(int x, int k) {
	bool r=1;
	int pre=0;
	for (int i = 0; i <= 19; i++){
        if (k & (1 << i)) {
        	chmin(r, (W[x] > pre));
        	chmin(r,inc[x][i]);
        	pre = lst[x][i];
        	prex=lst[x][i];
        	x = twok[x][i];
        }
        if (x <= -1) return r;
    }
    return r;
}
bool checkdec(int x, int k) {
	bool r=1;
	int pre=inf;
	for (int i = 0; i <= 19; i++){
        if (k & (1 << i)) {
        	chmin(r, (W[x] < pre));
        	chmin(r,decr[x][i]);
        	pre = lst[x][i];
        	prey=lst[x][i];
        	x = twok[x][i];
        	
        }
        if (x <= -1) return r;
    }
    return r;
}
 
bool lca(int x, int y){ // is edge weight increasing from x->y?
	bool r=1;
	prex=0,prey=inf;
    if (depth[x] > depth[y]) {
        int dd = depth[x] - depth[y];
       // reach
       	chmin(r, checkinc(x,dd));
       	if(!r)return 0;
        x = kth_parent(x, dd);
        
    } else {
        int dd = depth[y] - depth[x];
        //reach
        chmin(r,checkdec(y,dd));
       	if(!r)return 0;
        y = kth_parent(y, dd);
    }
    if (x == y) return r;
    
    
    for (int i = 19; i >= 0; i--){
        if (twok[x][i] != twok[y][i]){
            //x = twok[x][i];
            chmin(r, (W[x]>prex));
            chmin(r,inc[x][i]);
            prex=lst[x][i];
            x=twok[x][i];
            
            //y = twok[y][i];
            chmin(r, (W[y]<prey));
            chmin(r, decr[y][i]);
            prey=lst[y][i];
            y=twok[y][i];
            if(r==0)return 0;
        }
    }
    chmin(r, (W[x]>prex));
    chmin(r, (W[y]<prey));
    chmin(r, (W[x]<W[y]));
    return r;
}
 
struct ufds_ {
	int p[MAXN];
	ufds_() {
		iota(p,p+MAXN,0);
	}
	int find(int x) {
		if(x==p[x])return x;
		else return p[x]=find(p[x]);
	}
	void merge(int x, int y) {
		x=find(x); y=find(y);
		p[y]=x;
	}
	bool same(int x, int y) {
		x=find(x); y=find(y);
		return (x==y);
	}
} ufds;
int dp_inc[MAXN];
int dp_dec[MAXN];
vector<pi> events[MAXN];
vector<pi> nodequeries[MAXN];
vector<pi> thisnode[MAXN];
map<pi,int> mp;
int fw[MAXN];
void update(int x, int v) { // DO NOT call this function even for point update here!
    for (; x<MAXN; x+=x&(-x)) fw[x] += v; 
} 
void update(int x, int y, int v){
    update(x, v);
    update(y + 1, -v);
}
int sum(int x) {
    int res = 0;
    for(; x; x-=x&(-x)) res += fw[x];
    return res;
}
 
void dfs1(int x, int p) {
	st[x]=cnt++;
	sort(all(V[x]), [](pi x, pi y) {
		return W[x.f]>W[y.f];
	});
	if(x!=1) {
		if(W[x] > W[p]){
			dp_inc[x]=p;
			dp_dec[x]=dp_dec[p];
		} else {
			dp_dec[x]=p;
			dp_inc[x]=dp_inc[p];
		}
	} else {
		dp_inc[x]=dp_dec[x]=0;
	}
	for(auto v:V[x])if(v.f!=p) {
		dfs1(v.f,x);
	}
	en[x]=cnt-1;
}
 
void dfs2(int x, int p) {
 
	update(max(W[x],1ll),MAXN-1,1);
	events[dp_dec[x]].pb(pi(W[x],-1));
	/*
	db(x);
	FOR(i,1,10) cerr << sum(i) << ' ';*/
	sort(all(nodequeries[x]), [](pi x, pi y) {
		return st[x.f]>st[y.f];
	});
	int fi=V[x][0].f;
	if(V[x].size() == 1  && x!=1)goto finish;
	if(fi==p)fi=V[x][1].f;
	db2(x,fi);
	while(nodequeries[x].size()) {
		pi c=nodequeries[x].back();
		//db3(V[x][0].f, st[V[x][0].f], st[c.f]);
		if(st[fi]<=st[c.f] && st[c.f] <= en[fi]){
			db3(x,c.f,sum(c.s));
			mp[pi(x, c.s)] = sum(c.s);
			nodequeries[x].pop_back();
		} else {
			break;
		}
	}
	for(int i=0;i<(int)V[x].size();i++){
		if(V[x][i].f==p) continue;
		dfs2(V[x][i].f,x);
		if(V[x][i+1].f==fi)continue;
		if(i<V[x].size()-1) {
			while(nodequeries[x].size()) {
				pi c=nodequeries[x].back();
				if(st[V[x][i+1].f]<=st[c.f] && st[c.f] <= en[V[x][i+1].f]){
					
					mp[pi(x, c.s)] = sum(c.s);
					nodequeries[x].pop_back();
				} else {
					break;
				}
			}
		}
	}
	finish:;
	while(thisnode[x].size()) {
		pi c=thisnode[x].back();
		mp[pi(x,c.s)]=sum(c.s);
		thisnode[x].pop_back();
	}
	for(auto i:events[x]) {
		update(max(1ll,i.f),MAXN-1,i.s);
	}
	
}
 
int32_t main() 
{
	IAMSPEED
	memset(twok,-1,sizeof twok);
	cin >> n >> k;
	FOR(i,1,n)dp[i]=1;
	
	int q=n+k-1;
	FOR(i,1,q) {
		char op; cin >> op;
		if(op == 'S') {
			int a,b; cin >> a >> b;
			queries.pb(ti3(op,a,b));
		} else if(op=='Q') {
			int a,b; cin >> a >> b;
			queries.pb(ti3(op,a,b));
		} else {
			int d; cin >> d;
			queries.pb(ti3(op,d,-1));
		}
	}
	int t=0;
	for(auto x:queries) {
		++t;
		char op=g0(x);
		if(op == 'S') {
			int a=g1(x); int b=g2(x);
			V[a].pb(pi(b,t));
			V[b].pb(pi(a,t));
		} 
		
	}
	predfs(1,-1,0,0);
	dfs1(1,-1);
	int idx=0;
	for(auto qq:queries) {
		++idx;
		char op=g0(qq);
		if(op=='S') {
			int a=g1(qq); int b=g2(qq);
			ufds.merge(a,b);
			
		}
		else if(op == 'Q') {
			int a, d; a=g1(qq); d=g2(qq);
			if(ufds.same(a,d) == 0){
				out[idx]=0; continue;
			}
			if(lca(d,a)) {
				out[idx]=1;
			} else {
				out[idx]=0;
			}
		} else {
			int x=g1(qq);
			thisnode[x].pb(pi(x,idx));
			
			if(dp_inc[x]!=1)nodequeries[twok[dp_inc[x]][0]].pb(pi(x,idx));
		}
	}
	
	
	/* solve the C queries */
	dfs2(1,-1);
	idx=0;
	for(auto qq:queries) {
		++idx;
		char op=g0(qq);
		if(op=='S') {
			
		} else if(op == 'Q') {
			if(out[idx]==1)cout<<"yes\n";
			else cout << "no\n";
		} else {
			int x=g1(qq);
			db2(x,twok[dp_inc[x]][0]);
			db2(mp[pi(x,idx)], mp[pi(twok[dp_inc[x]][0], idx)]);
			bool notdone=0;
			
			if(dp_inc[x] != 0){
				if(W[dp_inc[x]]  > idx)notdone=1;
				//if(W[dp_inc[dp_inc[x]]] > idx)notdone=0;
				cout << notdone + mp[pi(x,idx)] - mp[pi(twok[dp_inc[x]][0],idx)] << '\n';
			}
			else cout << mp[pi(x,idx)] << '\n';
		}
	}
	
}

Compilation message

servers.cpp: In function 'void dfs2(long long int, long long int)':
servers.cpp:249:7: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  249 |   if(i<V[x].size()-1) {
      |      ~^~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 36572 KB Output is correct
2 Correct 51 ms 38248 KB Output is correct
3 Correct 62 ms 38344 KB Output is correct
4 Correct 54 ms 38472 KB Output is correct
5 Correct 59 ms 38164 KB Output is correct
6 Correct 70 ms 37788 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 36572 KB Output is correct
2 Correct 51 ms 38248 KB Output is correct
3 Correct 62 ms 38344 KB Output is correct
4 Correct 54 ms 38472 KB Output is correct
5 Correct 59 ms 38164 KB Output is correct
6 Correct 70 ms 37788 KB Output is correct
7 Incorrect 43 ms 37812 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 36612 KB Output is correct
2 Correct 203 ms 79348 KB Output is correct
3 Correct 215 ms 79292 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 47 ms 36612 KB Output is correct
2 Correct 203 ms 79348 KB Output is correct
3 Correct 215 ms 79292 KB Output is correct
4 Incorrect 47 ms 37588 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 36564 KB Output is correct
2 Correct 253 ms 99404 KB Output is correct
3 Correct 254 ms 99436 KB Output is correct
4 Correct 286 ms 100012 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 36564 KB Output is correct
2 Correct 253 ms 99404 KB Output is correct
3 Correct 254 ms 99436 KB Output is correct
4 Correct 286 ms 100012 KB Output is correct
5 Correct 45 ms 37684 KB Output is correct
6 Incorrect 346 ms 112568 KB Extra information in the output file
7 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36588 KB Output is correct
2 Correct 168 ms 78944 KB Output is correct
3 Correct 203 ms 79132 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36588 KB Output is correct
2 Correct 168 ms 78944 KB Output is correct
3 Correct 203 ms 79132 KB Output is correct
4 Incorrect 49 ms 37716 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 36636 KB Output is correct
2 Correct 267 ms 99416 KB Output is correct
3 Correct 237 ms 99480 KB Output is correct
4 Correct 265 ms 99976 KB Output is correct
5 Correct 40 ms 36576 KB Output is correct
6 Correct 176 ms 78936 KB Output is correct
7 Correct 204 ms 79184 KB Output is correct
8 Correct 298 ms 80044 KB Output is correct
9 Correct 257 ms 80080 KB Output is correct
10 Correct 344 ms 87976 KB Output is correct
11 Correct 365 ms 87072 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 36636 KB Output is correct
2 Correct 267 ms 99416 KB Output is correct
3 Correct 237 ms 99480 KB Output is correct
4 Correct 265 ms 99976 KB Output is correct
5 Correct 40 ms 36576 KB Output is correct
6 Correct 176 ms 78936 KB Output is correct
7 Correct 204 ms 79184 KB Output is correct
8 Correct 298 ms 80044 KB Output is correct
9 Correct 257 ms 80080 KB Output is correct
10 Correct 344 ms 87976 KB Output is correct
11 Correct 365 ms 87072 KB Output is correct
12 Correct 47 ms 37688 KB Output is correct
13 Incorrect 363 ms 112556 KB Extra information in the output file
14 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 36540 KB Output is correct
2 Correct 47 ms 38236 KB Output is correct
3 Correct 62 ms 38392 KB Output is correct
4 Correct 56 ms 38624 KB Output is correct
5 Correct 57 ms 38140 KB Output is correct
6 Correct 57 ms 37736 KB Output is correct
7 Correct 43 ms 36716 KB Output is correct
8 Correct 204 ms 79288 KB Output is correct
9 Correct 193 ms 79412 KB Output is correct
10 Correct 40 ms 36572 KB Output is correct
11 Correct 283 ms 99416 KB Output is correct
12 Correct 226 ms 99428 KB Output is correct
13 Correct 248 ms 99984 KB Output is correct
14 Correct 39 ms 36680 KB Output is correct
15 Correct 165 ms 79036 KB Output is correct
16 Correct 186 ms 79060 KB Output is correct
17 Correct 276 ms 79940 KB Output is correct
18 Correct 240 ms 80068 KB Output is correct
19 Correct 360 ms 88024 KB Output is correct
20 Correct 374 ms 87144 KB Output is correct
21 Correct 202 ms 77964 KB Output is correct
22 Correct 212 ms 78080 KB Output is correct
23 Correct 239 ms 78876 KB Output is correct
24 Correct 220 ms 78828 KB Output is correct
25 Correct 301 ms 84876 KB Output is correct
26 Correct 302 ms 78284 KB Output is correct
27 Correct 243 ms 78208 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 44 ms 36540 KB Output is correct
2 Correct 47 ms 38236 KB Output is correct
3 Correct 62 ms 38392 KB Output is correct
4 Correct 56 ms 38624 KB Output is correct
5 Correct 57 ms 38140 KB Output is correct
6 Correct 57 ms 37736 KB Output is correct
7 Correct 43 ms 36716 KB Output is correct
8 Correct 204 ms 79288 KB Output is correct
9 Correct 193 ms 79412 KB Output is correct
10 Correct 40 ms 36572 KB Output is correct
11 Correct 283 ms 99416 KB Output is correct
12 Correct 226 ms 99428 KB Output is correct
13 Correct 248 ms 99984 KB Output is correct
14 Correct 39 ms 36680 KB Output is correct
15 Correct 165 ms 79036 KB Output is correct
16 Correct 186 ms 79060 KB Output is correct
17 Correct 276 ms 79940 KB Output is correct
18 Correct 240 ms 80068 KB Output is correct
19 Correct 360 ms 88024 KB Output is correct
20 Correct 374 ms 87144 KB Output is correct
21 Correct 202 ms 77964 KB Output is correct
22 Correct 212 ms 78080 KB Output is correct
23 Correct 239 ms 78876 KB Output is correct
24 Correct 220 ms 78828 KB Output is correct
25 Correct 301 ms 84876 KB Output is correct
26 Correct 302 ms 78284 KB Output is correct
27 Correct 243 ms 78208 KB Output is correct
28 Incorrect 45 ms 37676 KB Extra information in the output file
29 Halted 0 ms 0 KB -