제출 #930480

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
930480		beaboss	늑대인간 (IOI18_werewolf)	C++14	0 / 100	314 ms	90436 KiB

werewolf

// Source: https://oj.uz/problem/view/IOI18_werewolf
// 

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

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

typedef vector<int> vi;

#define FOR(i, a, b) for (int i = (a); i<b; i++)

bool ckmin(int& a, int b){ return b < a ? a = b, true : false; }

bool ckmax(int& a, int b){ return b > a ? a = b, true : false; }


const int N = 2e5 + 10;

vpii adj[N];

vi p(N + 1, -1), id(N + 1);
int cnt = 0;
vector<vi> kadj(2 * N);


int get(int x) {
	return (p[x] > 0) ? x = get(p[x]) : x;
}

void unite(int x, int y) {
	x = get(x);
	y = get(y);

	if (x == y) return;

	if (-p[x] < -p[y]) swap(x, y);

	int here = cnt++;
	kadj[here].pb(id[x]);
	kadj[here].pb(id[y]);

	// cout << x << y << ' ' << here << ' ' << id[x] << ' ' << id[y] << endl;

	p[x] += p[y];
	p[y] = x;

	id[x] = here;
}
int tin = 0;
void dfs(int cur, vi &rep, vpii &range) {
	// cout << cur << endl;
	range[cur] = {5 * N, 0};
	if (kadj[cur].size() == 0) {
		rep[cur] = tin++;
		range[cur] = {rep[cur], rep[cur]};
		return;
	}
	for (auto val: kadj[cur]) {
		dfs(val, rep, range);
		ckmin(range[cur].f, range[val].f);
		ckmax(range[cur].s, range[val].s);
	}
}

void reorder(vi &rep, vpii &range, vector<vpii> &merge, vector<vpii> &need, vi &finalid) {
	// need is what we need to update at each stage of merge
	// final is the range for each
	FOR(i, 0, N) {
		p[i]=-1;
		id[i]=i;

	}

	FOR(i, 0, 2 * N) kadj[i].clear();

	cnt = N;

	FOR(i, 0, merge.size()) {
		

		for (auto val: merge[i]) {
			// pii val = merge[i];
			unite(val.f, val.s);
			// cout <<i << ' ' << val.f << ' ' << val.s << endl;
		}


		for (auto val: need[i]) {
			// cout << i << val.f << endl;
			finalid[val.s] = id[get(val.f)];
		}

		
	}

	tin = 0;
	dfs(cnt-1, rep, range);

	// FOR(i, 0, rep.size()) cout << rep[i] << endl;


}

vi bit(N + 1);

void update(int ind, int val) {
	ind++;
	for (; ind < N; ind += ind & -ind) bit[ind] += val;
}

int pref(int l) {
	if (l < 0) return 0;
	l++;
	int res = 0;
	for (; l > 0; l -= l & -l) res += bit[l];
	return res;
}

int query(int l, int r) {
	return pref(r) - pref(l - 1);
}

vi check_validity(int n, vi x, vi y, vi s, vi e, vi l, vi r) {

	FOR(i, 0, x.size()) {
		adj[max(x[i], y[i])].pb({x[i], y[i]});
	}

	vector<vpii> merge(n);
	vector<vpii> need(n);

	FOR(i, 0, r.size()) {
		need[r[i]].pb({e[i], i});
	}

	FOR(i, 0, N) {
		for (auto j: adj[i]) merge[i].pb(j);

	}

	vi rep1(n);
	vpii range(2 * N + 1);
	vi finalid(r.size());

	reorder(rep1, range, merge, need, finalid);

	vpii r1;
	FOR(i, 0, finalid.size()) r1.pb(range[finalid[i]]);

	vi rep2(n);

	FOR(i, 0, n) merge[i].clear();
	FOR(i, 0, n) merge[min(x[i], y[i])].pb({x[i], y[i]});


	reverse(merge.begin(), merge.end());
	FOR(i, 0, n) need[i].clear();

	FOR(i, 0, l.size()) {
		need[n-l[i]-1].pb({s[i], i});
	}

	reorder(rep2, range, merge, need, finalid);

	vpii r2;
	FOR(i, 0, finalid.size()) r2.pb(range[finalid[i]]);

	vi in_range(e.size(), 0);

	vector<vi> add(n);
	vector<vpii> sweep(n);


	FOR(i, 0, n) add[rep1[i]].pb(i);

	FOR(i, 0, e.size()) {
		if (r1[i].f) sweep[r1[i].f-1].pb({i, -1});
		sweep[r1[i].s].pb({i, 1});
	}

	FOR(i, 0, n) {
		for (auto val: add[i]) {
			// cout << rep2[val] << endl;
			update(rep2[val], 1);
		}
		for (auto val: sweep[i]) {

			// cout << r2[val.f].f << ' ' << r2[val.f].s << ' ' << query(r2[val.f].f, r2[val.f].s) << endl;
			in_range[val.f] += query(r2[val.f].f, r2[val.f].s) * val.s;
		}
	}
	
	vi res;
	FOR(i, 0, e.size()) res.pb(in_range[i] > 0);

	// FOR(i, 0, n) cout << rep1[i] << ' ' << rep2[i] << endl;
	// FOR(i, 0, e.size()) cout << r1[i].f << r1[i].s << ' ' << r2[i].f << r2[i].s << endl;

	return res;
	
	
}

// int main() {
// 	ios::sync_with_stdio(false);
// 	cin.tie(nullptr);

// 	vi ans = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
// {4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});

// 	for (auto val: ans) cout << val << endl;

// }

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

werewolf.cpp: In function 'void reorder(vi&, vpii&, std::vector<std::vector<std::pair<int, int> > >&, std::vector<std::vector<std::pair<int, int> > >&, vi&)':
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
   87 |  FOR(i, 0, merge.size()) {
      |      ~~~~~~~~~~~~~~~~~~                  
werewolf.cpp:87:2: note: in expansion of macro 'FOR'
   87 |  FOR(i, 0, merge.size()) {
      |  ^~~
werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  134 |  FOR(i, 0, x.size()) {
      |      ~~~~~~~~~~~~~~                      
werewolf.cpp:134:2: note: in expansion of macro 'FOR'
  134 |  FOR(i, 0, x.size()) {
      |  ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  141 |  FOR(i, 0, r.size()) {
      |      ~~~~~~~~~~~~~~                      
werewolf.cpp:141:2: note: in expansion of macro 'FOR'
  141 |  FOR(i, 0, r.size()) {
      |  ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  157 |  FOR(i, 0, finalid.size()) r1.pb(range[finalid[i]]);
      |      ~~~~~~~~~~~~~~~~~~~~                
werewolf.cpp:157:2: note: in expansion of macro 'FOR'
  157 |  FOR(i, 0, finalid.size()) r1.pb(range[finalid[i]]);
      |  ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  168 |  FOR(i, 0, l.size()) {
      |      ~~~~~~~~~~~~~~                      
werewolf.cpp:168:2: note: in expansion of macro 'FOR'
  168 |  FOR(i, 0, l.size()) {
      |  ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  175 |  FOR(i, 0, finalid.size()) r2.pb(range[finalid[i]]);
      |      ~~~~~~~~~~~~~~~~~~~~                
werewolf.cpp:175:2: note: in expansion of macro 'FOR'
  175 |  FOR(i, 0, finalid.size()) r2.pb(range[finalid[i]]);
      |  ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  185 |  FOR(i, 0, e.size()) {
      |      ~~~~~~~~~~~~~~                      
werewolf.cpp:185:2: note: in expansion of macro 'FOR'
  185 |  FOR(i, 0, e.size()) {
      |  ^~~
werewolf.cpp:19:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 | #define FOR(i, a, b) for (int i = (a); i<b; i++)
......
  203 |  FOR(i, 0, e.size()) res.pb(in_range[i] > 0);
      |      ~~~~~~~~~~~~~~                      
werewolf.cpp:203:2: note: in expansion of macro 'FOR'
  203 |  FOR(i, 0, e.size()) res.pb(in_range[i] > 0);
      |  ^~~

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