제출 #294059

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

werewolf

#include "werewolf.h"

#include <bits/stdc++.h>


#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 2e5 + 10;

int par[N], pos[N];
vector<int> C[N];
int Find(int u){
	if(par[u] == u) return u;
	return par[u] = Find(par[u]);
}
void Unite(int u, int v){
	u = Find(u);
	v = Find(v);
	if(u == v) return ;
	if(C[u].size() < C[v].size()) swap(u, v);
	par[v] = u;
	for(auto x : C[v]){
		pos[x] = C[u].size();
		C[u].pb(x);
	}
	C[v].clear();
}
int n;
vi G[N];

pii res[N], s1[N], s2[N];
vector<pii> Q[N];

vi dsuArray(vi ord){
	vi mk(n, 0);
	for(int i : ord){
		par[i] = i;
		C[i] = {i};
		pos[i] = 0;
		for(int adj : G[i])
			if(mk[adj]) Unite(adj, i);
		
		for(auto X : Q[i]){
			res[X.S] = {-pos[X.F], C[Find(X.F)].size() - pos[X.F]};
		}
		
		mk[i] = 1;
	}
	return C[Find(0)];
}
vi DR, DL;

int fen[N];
void Add(int idx){
	idx += 2;
	for(; idx < N; idx += idx & (-idx))
		fen[idx] ++;
}
int Get(int idx){
	idx += 2;
	int res = 0;
	for(; idx; idx -= idx & (-idx))
		res += fen[idx];
	return res;
}

vector< pair<pair<int, int>, int> > Qf[N]; // Z, idx, ans

vi check_validity(int _n, vi X, vi Y, vi S, vi E, vi L, vi R){
	n = _n;
	int m = X.size();
	int q = S.size();

	for(int i = 0; i < m; i++) G[X[i]].pb(Y[i]), G[Y[i]].pb(X[i]);

	vi O;
	for(int i = 0; i < n; i++) O.pb(i);
	for(int i = 0; i < n; i++) Q[i].clear();
	for(int i = 0; i < q; i++) Q[R[i]].pb({E[i], i});
	DR = dsuArray(O);
	for(int i = 0; i < q; i++) s1[i] = {res[i].F + pos[E[i]], res[i].S + pos[E[i]]};

	
	reverse(all(O));
	for(int i = 0; i < n; i++) Q[i].clear();
	for(int i = 0; i < q; i++) Q[L[i]].pb({S[i], i});
	DL = dsuArray(O);
	for(int i = 0; i < q; i++) s2[i] = {res[i].F + pos[S[i]], res[i].S + pos[S[i]]};

	//cerr << "! ";
	//for(auto x : DR) cerr << x << ' ';
	//cerr << '\n';
	//for(int i = 0; i < q; i++) cerr << "# " << s1[i].F << ' ' << s1[i].S << '\n';


	vi ans(q, 0);

	for(int i = 0; i < q; i++){
		bool fl = false;
		if(s1[i].S) Qf[s1[i].S - 1].pb({{+1, s2[i].S - 1}, i});
		if(s1[i].S) Qf[s1[i].S - 1].pb({{-1, s2[i].F - 1}, i});
		if(s1[i].F) Qf[s1[i].F - 1].pb({{-1, s2[i].S - 1}, i});
		if(s1[i].F) Qf[s1[i].F - 1].pb({{+1, s2[i].F - 1}, i});
	}
	vi inv(n, 0);
	for(int i = 0; i < n; i++)
		inv[DL[i]] = i;
	for(int i = 0; i < n; i++){
		Add(inv[DR[i]]);
		for(auto X : Qf[i]){
			ans[X.S] += X.F.F * Get(X.F.S);
		}
	}
	for(auto &x : ans)
		x = min(x, 1);
	return ans;
}

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

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:107:8: warning: unused variable 'fl' [-Wunused-variable]
  107 |   bool fl = false;
      |        ^~

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