| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 726020 |
2023-04-18T10:14:11 Z |
Cookie |
Werewolf (IOI18_werewolf) |
C++14 |
|
612 ms |
151612 KB |
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#include <cstdio>
#include <cstdlib>
#include <vector>
//#include "werewolf.h"
namespace {
int read_int() {
int x;
if (scanf("%d", &x) != 1) {
fprintf(stderr, "Error while reading input\n");
exit(1);
}
return x;
}
} // namespace
const int mxn = 7e5;
int pl[mxn + 1], pr[mxn + 1], n;
vt<int>adj[mxn + 1], adjl[mxn + 1], adjr[mxn + 1];
vt<pii>ql[mxn + 1], qr[mxn + 1];
int tonodel[mxn + 1], tonoder[mxn + 1], tt = 0;
int tinl[mxn + 1], toutl[mxn + 1], tinr[mxn + 1], toutr[mxn + 1], rootl[mxn + 1], rootr[mxn + 1];
int fpl(int u){
if(pl[u] == u)return(u);
return(pl[u] = fpl(pl[u]));
}
int fpr(int u){
if(pr[u] == u)return(u);
return(pr[u] = fpr(pr[u]));
}
void unonl(int u, int v){
v = fpl(v);
if(u == v)return;
pl[v] = u; adjl[u].pb(v);
}
void unonr(int u, int v){
v = fpr(v);
if(u == v)return;
pr[v] = u; adjr[u].pb(v);
}
void dfsl(int s){
if(s < n){
tinl[s] = ++tt; tonodel[tt] = s;
}
else tinl[s] = 2 * n;
for(auto i: adjl[s]){
dfsl(i); tinl[s] = min(tinl[s], tinl[i]);
}
toutl[s] = tt;
}
void buildl(){
for(int i = 0; i < n; i++)pl[i] = i;
for(int i = n - 1; i >= 0; i--){
int pos = n + i;
pl[pos] = pos;
unonl(pos, i);
for(auto j: adj[i]){
if(j > i){
unonl(pos, j);
}
}
for(auto [u, id]: ql[i]){
int U = fpl(u); rootl[id] = U;
}
}
pl[2 * n] = 2 * n;
for(int i = 0; i <= n - 1; i++){
unonl(2 * n, i);
}
dfsl(2 * n);
}
void dfsr(int s){
if(s < n){
tinr[s] = ++tt; tonoder[tt] = s;
}
else tinr[s] = 2 * n;
for(auto i: adjr[s]){
dfsr(i); tinr[s] = min(tinr[s], tinr[i]);
}
toutr[s] = tt;
}
void buildr(){
for(int i = 0; i < n; i++)pr[i] = i;
for(int i = 0; i < n; i++){
int pos = n + i; pr[pos] = pos;
unonr(pos, i);
for(auto j: adj[i]){
if(j < i){
unonr(pos, j);
}
}
if(i == 5){
}
for(auto [u, id]: qr[i]){
int U = fpr(u);
rootr[id] = U;
}
}
tt = 0; pr[2 * n] = 2 * n;
for(int i = 0; i < n; i++){
unonr(2 * n, i);
}
dfsr(2 * n);
}
struct Events{
int type, y, l, r, id;
bool operator <(const Events &b){
if(y == b.y){
return(type > b.type);
}
return(y < b.y);
}
};
int bit[mxn + 1], before[mxn + 1], after[mxn + 1];
void upd(int p, int v){
while(p <= mxn){
bit[p] += v;
p += p & (-p);
}
}
int get(int p){
int ans = 0;
while(p){
ans += bit[p];
p -= p & (-p);
}
return(ans);
}
vt<Events>events;
vt<int>check_validity(int N, vt<int>x, vt<int>y, vt<int>s, vt<int>e, vt<int>l, vt<int>r){
n = N;
for(int i = 0; i < x.size(); i++){
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
for(int i = 0; i < l.size(); i++){
ql[l[i]].pb(make_pair(s[i], i));
qr[r[i]].pb(make_pair(e[i], i));
}
buildl();
buildr();
for(int i = 0; i < l.size(); i++){
if(i == 1){
cout << rootr[i] << " ";
for(int j = tinr[rootr[i]] ; j <= toutr[rootr[i]]; j++){
cout << tonoder[j] << " ";
}
}
events.pb({1, tinr[rootr[i]], tinl[rootl[i]], toutl[rootl[i]], i});
events.pb({-1, toutr[rootr[i]], tinl[rootl[i]], toutl[rootl[i]], i});
}
for(int i = 0; i < n; i++){
events.pb({0, tinr[i], tinl[i], -1, -1});
}
sort(events.begin(), events.end());
for(auto [type, y, l, r, id]: events){
if(type == 0){
upd(l, 1);
}else if(type == 1){
before[id] = get(r) - get(l - 1);
}else{
after[id] = get(r) - get(l - 1);
}
}
vt<int>ans;
for(int i = 0; i < l.size(); i++){
ans.pb((bool)(before[i] < after[i]));
}
return(ans);
}
Compilation message
werewolf.cpp: In function 'void buildl()':
werewolf.cpp:81:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
81 | for(auto [u, id]: ql[i]){
| ^
werewolf.cpp: In function 'void buildr()':
werewolf.cpp:121:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
121 | for(auto [u, id]: qr[i]){
| ^
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:160:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
160 | for(int i = 0; i < x.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp:164:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for(int i = 0; i < l.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp:173:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int i = 0; i < l.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp:187:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
187 | for(auto [type, y, l, r, id]: events){
| ^
werewolf.cpp:198:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
198 | for(int i = 0; i < l.size(); i++){
| ~~^~~~~~~~~~
werewolf.cpp: At global scope:
werewolf.cpp:21:5: warning: 'int {anonymous}::read_int()' defined but not used [-Wunused-function]
21 | int read_int() {
| ^~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
82636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
82636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
612 ms |
151612 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
41 ms |
82636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
