oj.uz

Submission #654109

# Submission time Handle Problem Language Result Execution time Memory
654109 2022-10-30T01:27:34 Z kym Inside information (BOI21_servers) C++14
50 / 100
 370 ms 100912 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) {
	st[x]=cnt++;
	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);
	}
	en[x]=cnt-1;
	
}

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) {
	sort(all(V[x]), [](pi x, pi y) {
		return W[x.f]>W[y.f];
	});
	dbvp(V[x]);
	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);
	}
}

void dfs2(int x, int p) {
	db2(x,p);

	update(max(W[x],1ll),MAXN-1,1);
	events[dp_dec[x]].pb(pi(W[x],-1));
	sort(all(nodequeries[x]), [](pi x, pi y) {
		return st[x.f]>st[y.f];
	});
	dbvp(nodequeries[x]);
	while(nodequeries[x].size()) {
		pi c=nodequeries[x].back();
		db3(x,c.f,c.s);
		if(st[V[x][0].f]<=st[c.f] && st[c.f] <= en[V[x][0].f]){
			db3(x,c.s,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(i<V[x].size()-1) {
			db(x);
			while(nodequeries[x].size()) {
				pi c=nodequeries[x].back();
				db3(x,c.f,c.s);
				if(st[V[x][i+1].f]<=st[c.f] && st[c.f] <= en[V[x][i+1].f]){
					db3(x,c.s,sum(c.s));
					mp[pi(x, c.s)] = sum(c.s);
					nodequeries[x].pop_back();
				} else {
					break;
				}
			}
		}
	}
	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));
			db2(x,twok[dp_inc[x]][0]);
		}
	}
	
	
	/* solve the C queries */
	dfs2(1,-1);
	reach
	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(dp_inc[x],idx);
			db2(mp[pi(twok[dp_inc[x]][0],idx)], mp[pi(x,idx)]);
			if(dp_inc[x] != 0)cout <<  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:244: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]
  244 |   if(i<V[x].size()-1) {
      |      ~^~~~~~~~~~~~~~

Subtask #1
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37032 KB Output is correct
2 Correct 44 ms 39228 KB Output is correct
3 Correct 54 ms 39244 KB Output is correct
4 Correct 42 ms 39356 KB Output is correct
5 Correct 56 ms 39004 KB Output is correct
6 Correct 54 ms 38704 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37032 KB Output is correct
2 Correct 44 ms 39228 KB Output is correct
3 Correct 54 ms 39244 KB Output is correct
4 Correct 42 ms 39356 KB Output is correct
5 Correct 56 ms 39004 KB Output is correct
6 Correct 54 ms 38704 KB Output is correct
7 Incorrect 42 ms 38076 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 43 ms 37028 KB Output is correct
2 Correct 184 ms 81716 KB Output is correct
3 Correct 167 ms 81672 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 37028 KB Output is correct
2 Correct 184 ms 81716 KB Output is correct
3 Correct 167 ms 81672 KB Output is correct
4 Incorrect 43 ms 37932 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 36 ms 37008 KB Output is correct
2 Correct 216 ms 100376 KB Output is correct
3 Correct 230 ms 100396 KB Output is correct
4 Correct 241 ms 100888 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37008 KB Output is correct
2 Correct 216 ms 100376 KB Output is correct
3 Correct 230 ms 100396 KB Output is correct
4 Correct 241 ms 100888 KB Output is correct
5 Incorrect 40 ms 38128 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36940 KB Output is correct
2 Correct 169 ms 81816 KB Output is correct
3 Correct 251 ms 81892 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36940 KB Output is correct
2 Correct 169 ms 81816 KB Output is correct
3 Correct 251 ms 81892 KB Output is correct
4 Incorrect 53 ms 38120 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 46 ms 36972 KB Output is correct
2 Correct 329 ms 100404 KB Output is correct
3 Correct 337 ms 100464 KB Output is correct
4 Correct 370 ms 100912 KB Output is correct
5 Correct 46 ms 37052 KB Output is correct
6 Correct 195 ms 81668 KB Output is correct
7 Correct 186 ms 81892 KB Output is correct
8 Correct 239 ms 82808 KB Output is correct
9 Correct 232 ms 82860 KB Output is correct
10 Correct 277 ms 90212 KB Output is correct
11 Correct 361 ms 89476 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 36972 KB Output is correct
2 Correct 329 ms 100404 KB Output is correct
3 Correct 337 ms 100464 KB Output is correct
4 Correct 370 ms 100912 KB Output is correct
5 Correct 46 ms 37052 KB Output is correct
6 Correct 195 ms 81668 KB Output is correct
7 Correct 186 ms 81892 KB Output is correct
8 Correct 239 ms 82808 KB Output is correct
9 Correct 232 ms 82860 KB Output is correct
10 Correct 277 ms 90212 KB Output is correct
11 Correct 361 ms 89476 KB Output is correct
12 Incorrect 40 ms 38180 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37024 KB Output is correct
2 Correct 45 ms 39120 KB Output is correct
3 Correct 54 ms 39220 KB Output is correct
4 Correct 42 ms 39420 KB Output is correct
5 Correct 53 ms 39024 KB Output is correct
6 Correct 55 ms 38716 KB Output is correct
7 Correct 39 ms 36992 KB Output is correct
8 Correct 175 ms 81676 KB Output is correct
9 Correct 178 ms 81708 KB Output is correct
10 Correct 35 ms 37052 KB Output is correct
11 Correct 233 ms 100316 KB Output is correct
12 Correct 223 ms 100460 KB Output is correct
13 Correct 249 ms 100892 KB Output is correct
14 Correct 37 ms 37000 KB Output is correct
15 Correct 156 ms 81748 KB Output is correct
16 Correct 178 ms 81904 KB Output is correct
17 Correct 241 ms 82736 KB Output is correct
18 Correct 226 ms 82732 KB Output is correct
19 Correct 289 ms 90284 KB Output is correct
20 Correct 343 ms 89424 KB Output is correct
21 Correct 191 ms 80868 KB Output is correct
22 Correct 183 ms 80980 KB Output is correct
23 Correct 203 ms 81728 KB Output is correct
24 Correct 201 ms 81740 KB Output is correct
25 Correct 249 ms 87004 KB Output is correct
26 Correct 215 ms 81200 KB Output is correct
27 Correct 208 ms 80988 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 36 ms 37024 KB Output is correct
2 Correct 45 ms 39120 KB Output is correct
3 Correct 54 ms 39220 KB Output is correct
4 Correct 42 ms 39420 KB Output is correct
5 Correct 53 ms 39024 KB Output is correct
6 Correct 55 ms 38716 KB Output is correct
7 Correct 39 ms 36992 KB Output is correct
8 Correct 175 ms 81676 KB Output is correct
9 Correct 178 ms 81708 KB Output is correct
10 Correct 35 ms 37052 KB Output is correct
11 Correct 233 ms 100316 KB Output is correct
12 Correct 223 ms 100460 KB Output is correct
13 Correct 249 ms 100892 KB Output is correct
14 Correct 37 ms 37000 KB Output is correct
15 Correct 156 ms 81748 KB Output is correct
16 Correct 178 ms 81904 KB Output is correct
17 Correct 241 ms 82736 KB Output is correct
18 Correct 226 ms 82732 KB Output is correct
19 Correct 289 ms 90284 KB Output is correct
20 Correct 343 ms 89424 KB Output is correct
21 Correct 191 ms 80868 KB Output is correct
22 Correct 183 ms 80980 KB Output is correct
23 Correct 203 ms 81728 KB Output is correct
24 Correct 201 ms 81740 KB Output is correct
25 Correct 249 ms 87004 KB Output is correct
26 Correct 215 ms 81200 KB Output is correct
27 Correct 208 ms 80988 KB Output is correct
28 Incorrect 46 ms 38064 KB Extra information in the output file
29 Halted 0 ms 0 KB -