제출 #791037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
791037		aymanrs	늑대인간 (IOI18_werewolf)	C++14	100 / 100	817 ms	157116 KiB

werewolf

#include<bits/stdc++.h>
using namespace std;
struct node {
	vector<node*> l;
	int a;
	bool v = false;
};
struct vert{
	vector<vert*> l;
	int t, e, ti;
	set<int>* s;
	vector<int> q, Q;
};
int f(int i, int r[]){
	if(r[i] == i) return i;
	return r[i] = f(r[i], r);
}
void merge(int a, int b, int r[], int s[]){
	a = f(a, r);
	b = f(b, r);
	if(a == b) return;
	if(s[a] > s[b]){
		r[b] = a;
		s[a] += s[b];
	} else {
		r[a] = b;
		s[b] += s[a];
	}
}
int t;
vector<vert*> F;
vector<int> L, R;
void dfsH(vert* n, map<int, vert*>& cur){
	cur[n->e] = n;
	n->t = t++;
	for(int i : n->q) F[i] = cur.lower_bound(L[i])->second;
	for(vert* c : n->l) dfsH(c, cur);
	cur.erase(n->e);
	n->e = t;
}
void dfsW(vert* n, map<int, vert*>& cur){
	cur[n->e] = n;
	vert* mc = NULL;
	int mx = -1;
	n->t = t++;
	for(vert* c : n->l){
		dfsW(c, cur);
		if(c->e-c->t > mx) {
			mx = c->e - c->t;
			mc = c;
		}
	}
	if(mx == -1){
		n->s = new set<int> ();
		n->s->insert(n->ti);
	} else {
		n->s = mc->s;
		n->s->insert(n->ti);
		for(vert* c : n->l){
			if(c == mc) continue;
			for(int i : *c->s) n->s->insert(i);
		}
	}
	for(int i : n->q) prev(cur.lower_bound(R[i]+1))->second->Q.push_back(i);
	for(int i : n->Q){
		auto p = n->s->lower_bound(F[i]->t);
		if(p != n->s->end() && *p < F[i]->e) L[i]=1;
		else L[i] = 0;
	}
	cur.erase(n->e);
	n->e = t;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int>LT, vector<int> RT){
	t = 0;
	L = LT;
	R = RT;
	F.resize(S.size());
	node g[N];
	vert m[N], M[N];
	int r[N], sz[N], c[N];
	for(int i = 0;i < N;i++) {
		m[i].e = M[i].e = i;
		g[i].a = i;
		r[i] = c[i] = i;
		sz[i] = 1;
	}
	for(int i = 0;i < X.size();i++) {
		g[X[i]].l.push_back(&g[Y[i]]);
		g[Y[i]].l.push_back(&g[X[i]]);
	}
	for(int j = 0;j < N;j++){
		node* d = &g[j];
		d->v = true;
		for(node* x : d->l){
			if(!x->v || f(x->a, r) == f(j, r)) continue;
			M[j].l.push_back(&M[c[f(x->a, r)]]);
			merge(x->a, j, r, sz);
			c[f(j, r)] = j;
		}
	}
	for(int i = 0;i < N;i++) {
		r[i] = c[i] = i;
		sz[i] = 1;
		g[i].v = false;
	}
	for(int j = N-1;j >= 0;j--){
		node* d = &g[j];
		d->v = true;
		for(node* x : d->l){
			if(!x->v || f(x->a, r) == f(j, r)) continue;
			m[j].l.push_back(&m[c[f(x->a, r)]]);
			merge(x->a, j, r, sz);
			c[f(j, r)] = j;
		}
	}
	for(int i = 0;i < S.size();i++){
		m[S[i]].q.push_back(i);
		M[E[i]].q.push_back(i);
	}
	map<int, vert*> cur;
	dfsH(&m[0], cur);
	for(int i = 0;i < N;i++) M[i].ti = m[i].t;
	dfsW(&M[N-1], cur);
	return L;
}

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

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:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |  for(int i = 0;i < X.size();i++) {
      |                ~~^~~~~~~~~~
werewolf.cpp:116:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |  for(int i = 0;i < S.size();i++){
      |                ~~^~~~~~~~~~

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