Submission #513827

#	Time	Username	Problem	Language	Result	Execution time	Memory
513827		AdamGS	Werewolf (IOI18_werewolf)	C++17	34 / 100	746 ms	97980 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=2e5+7, LG=20;
vi V[LIM], pytania[LIM], dodaj[LIM];
vector<pair<int,int>>kraw;
set<int>zbior[LIM];
int Fl[LIM], pocz[LIM], kon[LIM], nxt[LIM][LG], lpre;
int Fr[LIM], ile[LIM];
int n, m;
int fndl(int x) {
	if(Fl[x]==x) return x;
	return Fl[x]=fndl(Fl[x]);
}
void unil(int a, int b) {
	a=fndl(a);
	b=fndl(b);
	if(a==b) return;
	Fl[b]=a;
	V[a].pb(b);
}
void DFS(int x) {
	++lpre;
	pocz[x]=lpre;
	for(auto i : V[x]) {
		nxt[i][0]=x;
		DFS(i);
	}
	kon[x]=lpre;
}
int poddrzewo(int v, int l) {
	for(int i=LG-1; i>=0; --i) if(nxt[v][i]>=l) v=nxt[v][i];
	return v;
}
int fndr(int x) {
	if(Fr[x]==x) return x;
	return fndr(Fr[x]);
}
void unir(int a, int b) {
	a=fndr(a);
	b=fndr(b);
	if(ile[a]<ile[b]) swap(a, b);
	for(auto i : zbior[b]) zbior[a].insert(i);
	zbior[b].clear();
	ile[a]+=ile[b];
	Fr[b]=a;
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
	n=N;
	m=X.size();
	rep(i, n) Fl[i]=i;
	rep(i, m) {
		if(X[i]>Y[i]) swap(X[i], Y[i]);
		kraw.pb({X[i], Y[i]});
	}
	sort(all(kraw));
	reverse(all(kraw));
	for(auto i : kraw) unil(i.st, i.nd);
	DFS(0);
	for(int j=1; j<LG; ++j) {
		rep(i, n) nxt[i][j]=nxt[nxt[i][j-1]][j-1];
	}
	rep(i, S.size()) pytania[R[i]].pb(i);
	vi ans(S.size());
	rep(i, n) {
		Fr[i]=i;
		ile[i]=1;
		zbior[i].insert(pocz[i]);
	}
	rep(i, m) dodaj[kraw[i].nd].pb(kraw[i].st);
	rep(i, n) {
		for(auto j : dodaj[i]) unir(i, j);
		for(auto j : pytania[i]) {
			int p=poddrzewo(S[j], L[j]);
			int x=fndr(E[j]);
			auto it=zbior[x].lower_bound(pocz[p]);
			if(it==zbior[x].end()) continue;
			auto a=*it;
			if(a<=kon[p]) ans[j]=1;
		}
	}
	return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'vi check_validity(int, vi, vi, vi, vi, vi, vi)':
werewolf.cpp:7:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
werewolf.cpp:71:2: note: in expansion of macro 'rep'
   71 |  rep(i, S.size()) pytania[R[i]].pb(i);
      |  ^~~

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