제출 #654109

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654109		kym	Inside information (BOI21_servers)	C++14	50 / 100	370 ms	100912 KiB

servers

#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';
		}
	}
	
}

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

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
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5