제출 #815771

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
815771		Lobo	늑대인간 (IOI18_werewolf)	C++17	100 / 100	676 ms	131860 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
const int inf = 1e9+10;
const int maxn = 4e5+10;
const int lg = 19;

int n, tin[2][maxn], tout[2][maxn], timer, tr[4*maxn];
int ds[2][maxn], dsz[2][maxn];
pair<int,int> p[2][lg+1][maxn];
vector<pair<int,int>> g[2][maxn];

int find(int id, int v) {
	if(ds[id][v] == v) return v;
	return ds[id][v] = find(id,ds[id][v]);
}

void join(int id, int u, int v, int w) {
	u = find(id,u);
	v = find(id,v);
	if(u == v) return;
	if(dsz[id][u] < dsz[id][v]) swap(u,v);
	//cout << id << " " << u << " " << v << " " << w << endl;

	ds[id][v] = u;
	dsz[id][u]+= dsz[id][v];
	g[id][u].pb(mp(w,v));
	p[id][0][v] = mp(u,w);
}

void dfseulertour(int id, int u, int ant) {
	tin[id][u] = ++timer;
	for(auto V : g[id][u]) if(V.sc != ant) {
		int v = V.sc;
		int w = V.fr;
		dfseulertour(id,v,u);
	}
	tout[id][u] = timer;
}

void upd(int no, int l, int r, int pos, int val) {
	if(l > pos || r < pos) return;
	if(l == r) {
		tr[no] = val;
		return;
	}
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	upd(lc,l,mid,pos,val);
	upd(rc,mid+1,r,pos,val);
	tr[no] = min(tr[lc],tr[rc]);
}

int query(int no, int l, int r, int L, int R) {
	if(l > R || r < L) return inf;
	if(l >= L && r <= R) return tr[no];
	int lc=2*no,rc=2*no+1,mid=(l+r)>>1;
	return min(query(lc,l,mid,L,R),query(rc,mid+1,r,L,R));
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {
  // int Q = S.size();
  // std::vector<int> A(Q);
  // for (int i = 0; i < Q; ++i) {
  //   A[i] = 0;
  // }
  // return A;

    n = N;
    for(int i = 0; i < n; i++) {
    	ds[0][i] = ds[1][i] = i;
    	dsz[0][i] = dsz[1][i] = 1;
    	p[0][0][i] = p[1][0][i] = mp(i,i);
    }

    vector<pair<int,pair<int,int>>> edgs0;
    for(int i = 0; i < (int) X.size(); i++) {
    	int u = X[i];
    	int v = Y[i];
    	edgs0.pb(mp(min(u,v),mp(u,v)));
    }

    sort(all(edgs0),greater<pair<int,pair<int,int>>>());

    for(auto X : edgs0) {
    	int w = X.fr;
    	int u = X.sc.fr;
    	int v = X.sc.sc;
    	join(0,u,v,w);
    }

    vector<pair<int,pair<int,int>>> edgs1;
    for(int i = 0; i < (int) X.size(); i++) {
    	int u = X[i];
    	int v = Y[i];
    	edgs1.pb(mp(max(u,v),mp(u,v)));
    }

    sort(all(edgs1));

    for(auto X : edgs1) {
    	int w = X.fr;
    	int u = X.sc.fr;
    	int v = X.sc.sc;
    	join(1,u,v,w);
    }

    for(int id = 0; id <= 1; id++) {
	    for(int b = 1; b <= lg; b++) {
	    	for(int i = 0; i < n; i++) {
	    		p[id][b][i].fr = p[id][b-1][p[id][b-1][i].fr].fr;
	    		if(id == 0) p[id][b][i].sc = min(p[id][b-1][p[id][b-1][i].fr].sc,p[id][b-1][i].sc);
	    		else p[id][b][i].sc = max(p[id][b-1][p[id][b-1][i].fr].sc,p[id][b-1][i].sc);
	    	}
	    }
	}

	timer = 0; dfseulertour(0,find(0,0),-1);
	timer = 0; dfseulertour(1,find(1,0),-1);
	vector<pair<pair<pair<int,int>,pair<int,int>>,int>> qrys;
	for(int i = 0; i < S.size(); i++) {
		int lbs = 0;
		int rbs = 0;
		int s = S[i];

		for(int b = lg; b >= 0; b--) {
			// cout << s << "  " << p[0][s][b].sc << endl;
			if(p[0][b][s].sc >= L[i]) {
				s = p[0][b][s].fr;
			}
		}

		int ls = tin[0][s];
		int rs = tin[0][s];
		lbs = 0;
		rbs = (int) g[0][s].size()-1;
		while(lbs <= rbs) {
			int mid = (lbs+rbs)/2;
			if(g[0][s][mid].fr >= L[i]) {
				rs = tout[0][g[0][s][mid].sc];
				lbs = mid+1;
			}
			else {
				rbs = mid-1;
			}
		}

		// cout << s << " " << ls << " " << rs << endl;

		int e = E[i];

		for(int b = lg; b >= 0; b--) {
			if(p[1][b][e].sc <= R[i]) {
				e = p[1][b][e].fr;
			}
		}

		int le = tin[1][e];
		int re = tin[1][e];
		lbs = 0;
		rbs = (int) g[1][e].size()-1;
		while(lbs <= rbs) {
			int mid = (lbs+rbs)/2;
			if(g[1][e][mid].fr <= R[i]) {
				re = tout[1][g[1][e][mid].sc];
				lbs = mid+1;
			}
			else {
				rbs = mid-1;
			}
		}

		// cout << le << " " << re << endl;

		qrys.pb(mp(mp(mp(le,re),mp(ls,rs)),i));
	}

	for(int i = 0; i < n; i++) {
		qrys.pb(mp(mp(mp(tin[1][i],inf),mp(i,-1)),0));
		upd(1,1,n,tin[0][i],tin[1][i]);
		//cout  << "  " << tin[0][i] << " " << tin[1][i] << endl;
	}

	sort(all(qrys));

	vector<int32_t> ans((int) S.size());
	for(auto X : qrys) {
		if(X.fr.sc.sc == -1) {
			int v = X.fr.sc.fr;
			upd(1,1,n,tin[0][v],inf);
		}
		else {
			int ls = X.fr.sc.fr;
			int rs = X.fr.sc.sc;
			int re = X.fr.fr.sc;
			int idqry = X.sc;

			//cout << query(1,1,n,ls,rs) << endl;
			if(query(1,1,n,ls,rs) <= re) {
				ans[idqry] = 1;
			}
			else {
				ans[idqry] = 0;
			}
		}
	}

	return ans;
}

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

werewolf.cpp: In function 'void dfseulertour(int, int, int)':
werewolf.cpp:40:7: warning: unused variable 'w' [-Wunused-variable]
   40 |   int w = V.fr;
      |       ^
werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:127:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |  for(int i = 0; i < S.size(); i++) {
      |                 ~~^~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51