Submission #340307

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
340307	2020-12-27 12:00:34	nikatamliani	Werewolf (IOI18_werewolf)	C++14	100 / 100	1977 ms	179692 KiB

werewolf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
const int NAX = 4e5+10, LG = 20;
vector<int> edges[NAX], tree[2][NAX], arr[2], ids; 
int in[2][NAX], out[2][NAX], p[2][NAX], L[2][NAX][LG];
int timer;
void add_edge(int x, int y, int which) {
  tree[which][x].push_back(y);
  tree[which][y].push_back(x); 
}
int find_set(int x, int which) {
  return x == p[which][x] ? x : p[which][x] = find_set(p[which][x], which);
}
void union_sets(int x, int y, int which) {
  x = find_set(x, which);
  y = find_set(y, which);
  if(x == y) {
    return;
  }
  p[which][y] = x; 
  add_edge(x, y, which);
}
void dfs(int x, int p, int which) {
  in[which][x] = ++timer;
  L[which][x][0] = p; 
  arr[which].push_back(x);
  for(int i = 1; i < LG; ++i) {
    int up = L[which][x][i - 1];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

werewolf.cpp: In member function 'int node::less(int)':
werewolf.cpp:68:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   68 |    int m = l + r >> 1;
      |            ~~^~~
werewolf.cpp: In function 'void build(int, int, int)':
werewolf.cpp:83:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |   int m = l + r >> 1;
      |           ~~^~~
werewolf.cpp: In function 'int query(int, int, int, int, int, int)':
werewolf.cpp:96:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   96 |  int m = l + r >> 1;
      |          ~~^~~
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:100:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |  for(int i = 0; i < X.size(); ++i) {
      |                 ~~^~~~~~~~~~

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