| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 982912 |
2024-05-15T03:14:57 Z |
wood |
Werewolf (IOI18_werewolf) |
C++17 |
|
136 ms |
44932 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R){
int m = X.size(), q =S.size();
//turn graph into array
vi adj[N];
for(int i = 0; i<m; i++){
adj[X[i]-1].pb(Y[i]-1);
adj[Y[i]-1].pb(X[i]-1);
}
vi arr;
int inds[N];
for (size_t i = 0; i < N; i++)
{
if(adj[i].size()==1){
int cur = i, prev = i;
inds[i] = arr.size();
arr.pb(i);
int next;
while(arr.size()<N){
for(int x : adj[cur]){
if(x!=prev){
next = x;
inds[x] = arr.size();
arr.pb(x);
}
}
prev = cur;
cur = next;
}
break;
}
}
//split intervals into forwards and backwards
using t = tuple<int,int,int>;
vector<t> forw, back;
for (size_t i = 0; i < q; i++)
{
if(inds[S[i]-1]<inds[E[i]-1]) forw.eb(S[i]-1,E[i]-1,i);
else back.eb(S[i]-1,E[i]-1,i);
}
//sort forw and back depending on their start position
sort(forw.begin(),forw.end(),[&](t l, t r){return get<0>(l)<get<0>(r);});
sort(back.begin(),back.end(),[&](t l, t r){return get<1>(l)<get<1>(r);});
//for forw look for the first instance bigger than r for back look at the first instance smaller than l
p32 res[q];
priority_queue<p32> l,r;
auto f = forw.begin(), b = back.begin();
for (size_t j = 0; j < N; j++)
{
int i = arr[j];
while(f!=forw.end()&&get<0>(*f)==i){
r.emplace(-R[get<2>(*f)],get<2>(*f));
f++;
}
while(b!=back.end()&&get<1>(*b)==i){
l.emplace(L[get<2>(*b)],get<2>(*b));
b++;
}
while(!r.empty()&&i>-r.top().fi-1){
res[r.top().se].se = j-1;
r.pop();
}
while(!l.empty()&&i<l.top().fi-1){
res[l.top().se].se = j-1;
l.pop();
}
}
//empty both queues
while(!r.empty()){
res[r.top().se].se = INT_MAX;
r.pop();
}
while(!l.empty()){
res[l.top().se].se = INT_MAX;
l.pop();
}
//sort forw and back depending on their end position
sort(forw.begin(),forw.end(),[&](t l, t r){return get<1>(l)<get<1>(r);});
sort(back.begin(),back.end(),[&](t l, t r){return get<0>(l)<get<0>(r);});
//do the opposite: first instance smaller than l for forw and first instance bigger than r for back
auto rf = forw.rbegin(), rb = back.rbegin();
for (int j = N - 1; j >= 0; j--)
{
int i = arr[j];
while(rf!=forw.rend()&&get<1>(*rf)==i){
l.emplace(L[get<2>(*rf)],get<2>(*rf));
rf++;
}
while(rb!=back.rend()&&get<0>(*rb)==i){
r.emplace(-R[get<2>(*rb)],get<2>(*rb));
rb++;
}
while(!r.empty()&&i>-r.top().fi-1){
res[r.top().se].fi = j+1;
r.pop();
}
while(!l.empty()&&i<l.top().fi-1){
res[l.top().se].fi = j+1;
l.pop();
}
}
while(!r.empty()){
res[r.top().se].fi = INT_MIN;
r.pop();
}
while(!l.empty()){
res[l.top().se].fi = INT_MIN;
l.pop();
}
vi result;
for (size_t i = 0; i < q; i++)
result.pb(res[i].se>=inds[min(S[i],E[i])-1]&&res[i].fi<=inds[max(S[i],E[i])-1]&&res[i].fi<=res[i].se);
return result;
}
// int main()
// {
// fast_cin();
// #ifndef ONLINE_JUDGE
// #ifdef _WIN32
// freopen("input.in", "r", stdin);
// freopen("input.out", "w", stdout);
// #endif
// #endif
// for(int i : check_validity(4,{1,2,4},{2,4,3},{1,3},{4,3},{2,2},{2,3})) cout<<i<<' ';
// return 0;
// }
Compilation message
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:35:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
35 | for (size_t i = 0; i < N; i++)
| ~~^~~
werewolf.cpp:42:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
42 | while(arr.size()<N){
| ~~~~~~~~~~^~
werewolf.cpp:59:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
59 | for (size_t i = 0; i < q; i++)
| ~~^~~
werewolf.cpp:71:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
71 | for (size_t j = 0; j < N; j++)
| ~~^~~
werewolf.cpp:134:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
134 | for (size_t i = 0; i < q; i++)
| ~~^~~
werewolf.cpp:41:17: warning: 'next' may be used uninitialized in this function [-Wmaybe-uninitialized]
41 | int next;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
136 ms |
44932 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
