| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 766183 |
2023-06-25T11:08:06 Z |
Nonoze |
Werewolf (IOI18_werewolf) |
C++17 |
|
4000 ms |
34744 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
//Subtask 1+2
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int Q = S.size(), M=X.size();
vector<int> A(Q, 0);
vector<int> adj[N];
for (int i = 0; i < M; ++i)
{
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
for (int i = 0; i < Q; ++i)
{
queue<pair<int, bool>> q;
map<pair<int, bool>, bool> visited;
q.push({S[i], 0});
while(!q.empty()) {
int x=q.front().first;
bool boolean=q.front().second;
q.pop();
if (visited.count({x, boolean}) || (x<L[i] && boolean==0) || (x<R[i] && boolean==1)) continue;
if (x==E[i] && boolean==1)
{
A[i]=1;
break;
}
visited[{x, boolean}]=true;
for (auto u: adj[x]) {
if (u>=L[i] && u<=R[i] && !boolean) q.push({u, 1});
q.push({u, boolean});
}
}
}
return A;
}
//Subtask 3
/***********************
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct node
{
node* left, *right;
int mini, maxi;
void update() {
mini=min(left->mini, right->mini);
maxi=max(left->maxi, right->maxi);
}
};
int querymin(node* root, int left, int right, int qLeft, int qRight, int val)
{
if (left>qRight || right<qLeft) return -1;
if (left==right) return (root->mini<val?left:-1);
int mid=(left+right)/2;
if (left>=qLeft && right<=qRight) {
if (root->left->mini<val)
{
return querymin(root->left, left, mid, qLeft, qRight, val);
}
if (root->right->mini<val)
{
return querymin(root->right, mid+1, right, qLeft, qRight, val);
}
return -1;
}
int s1=querymin(root->left, left, mid, qLeft, qRight, val);
if (s1!=-1) return s1;
return querymin(root->right, mid+1, right, qLeft, qRight, val);
}
int querymax(node* root, int left, int right, int qLeft, int qRight, int val)
{
if (left>qRight || right<qLeft) return -1;
if (left==right) return (root->maxi>val?left:-1);
int mid=(left+right)/2;
if (left>=qLeft && right<=qRight) {
if (root->right->maxi>val)
{
return querymax(root->right, mid+1, right, qLeft, qRight, val);
}
if (root->left->maxi>val)
{
return querymax(root->left, left, mid, qLeft, qRight, val);
}
return -1;
}
int s1=querymax(root->right, mid+1, right, qLeft, qRight, val);
if (s1!=-1) return s1;
return querymax(root->left, left, mid, qLeft, qRight, val);
}
void build(node* root, int left, int right, vector<int>& v)
{
if (left==right) {
root->mini=root->maxi=v[left];
return;
}
root->left=new node{NULL, NULL, (int)v.size(), 0};
root->right=new node{NULL, NULL, (int)v.size(), 0};
int mid=(left+right)/2;
build(root->left, left, mid, v);
build(root->right, mid+1, right, v);
root->update();
return;
}
void destroy(node *root) {
if (root->left) destroy(root->left);
if (root->right) destroy(root->right);
delete root;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int Q = S.size();
vector<int> A(Q);
vector<int> cities;
vector<int> empl(N);
vector<bool> verif(N, false);
vector<int> adj[N];
for (int i = 0; i < (int)X.size(); ++i)
{
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int curr=-1;
for (int i = 0; i < N; ++i)
{
if (adj[i].size()==1)
{
curr=i;
break;
}
}
for (int i = 0; i < N; ++i)
{
cities.push_back(curr);
empl[curr]=i;
if (adj[adj[curr][0]][0]==curr && adj[adj[curr][0]].size()>=2)
{
swap(adj[adj[curr][0]][0], adj[adj[curr][0]][1]);
}
curr=adj[curr][0];
}
node *root=new node{NULL, NULL, N, 0};
node *root2=new node{NULL, NULL, N, 0};
build(root, 0, N-1, cities);
reverse(cities.begin(), cities.end());
build(root2, 0, N-1, cities);
for (int i = 0; i < Q; ++i) {
int human=-1;
int wolf=-1;
E[i]=empl[E[i]];
S[i]=empl[S[i]];
if (E[i]<S[i])
{
S[i]=N-S[i]-1;
E[i]=N-E[i]-1;
human=querymax(root2, 0, N-1, S[i], E[i], R[i]);
wolf=querymin(root2, 0, N-1, S[i], E[i], L[i]);
} else {
human=querymax(root, 0, N-1, S[i], E[i], R[i]);
wolf=querymin(root, 0, N-1, S[i], E[i], L[i]);
}
if (human==-1) {
if (wolf==-1 || wolf>S[i]) {
A[i]=1;
} else {
A[i]=0;
}
} else if (wolf==-1) {
if (human<E[i]) {
A[i]=1;
} else {
A[i]=0;
}
}
else if (human+1<wolf) {
A[i]=1;
} else A[i]=0;
}
return A;
}*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4056 ms |
34744 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
