oj.uz

Submission #513827

# Submission time Handle Problem Language Result Execution time Memory
513827 2022-01-17T16:57:22 Z AdamGS Werewolf (IOI18_werewolf) C++17
34 / 100
 746 ms 97980 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 746 ms 88496 KB Output is correct
2 Correct 486 ms 85524 KB Output is correct
3 Correct 474 ms 84520 KB Output is correct
4 Correct 522 ms 84424 KB Output is correct
5 Correct 540 ms 84552 KB Output is correct
6 Correct 597 ms 85168 KB Output is correct
7 Correct 685 ms 86704 KB Output is correct
8 Correct 447 ms 85380 KB Output is correct
9 Correct 378 ms 85144 KB Output is correct
10 Correct 373 ms 82328 KB Output is correct
11 Correct 394 ms 82480 KB Output is correct
12 Correct 527 ms 86144 KB Output is correct
13 Correct 532 ms 97936 KB Output is correct
14 Correct 548 ms 97896 KB Output is correct
15 Correct 589 ms 97884 KB Output is correct
16 Correct 590 ms 97980 KB Output is correct
17 Correct 714 ms 86724 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 23756 KB Output isn't correct
2 Halted 0 ms 0 KB -