| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 84638 |
2018-11-16T09:47:32 Z |
KLPP |
Werewolf (IOI18_werewolf) |
C++14 |
|
4000 ms |
359700 KB |
#include "werewolf.h"
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long int lld;
typedef pair<int,int> pii;
class DSU{
int parent[1000000];
int root[1000000];
int ST[1000000][32];
vector<int> child[1000000];
int TOP;
int MOD;
int N;
public:
vector<int> Tour;
int first[1000000];
int last[1000000];
void init(int n, int mod){
N=n;
for(int i=0;i<n;i++){
parent[i]=i;
root[i]=i;
first[i]=-1;
last[i]=-1;
}
MOD=mod;
}
int Root(int x){
if(x==root[x])return x;
root[x]=Root(root[x]);
return root[x];
}
void merge(int a, int b){
a=Root(a);
b=Root(b);
if(a==b)return;
if(MOD){
if(a<b){
parent[a]=b;
root[a]=b;
}else{
parent[b]=a;
root[b]=a;
}
return;
}
if(a<b){
parent[b]=a;
root[b]=a;
}else{
parent[a]=b;
root[a]=b;
}
return;
}
void arrange(){
for(int i=0;i<N;i++){
if(parent[i]!=i){
child[parent[i]].push_back(i);
}else TOP=i;
}
for(int i=0;i<N;i++){
ST[i][0]=parent[i];
}
for(int j=1;j<32;j++){
for(int i=0;i<N;i++){
ST[i][j]=ST[ST[i][j-1]][j-1];
}
}
}
void DFS(int node){
first[node]=Tour.size();
Tour.push_back(node);
for(int i=0;i<child[node].size();i++){
DFS(child[node][i]);
//Tour.push_back(node);
}
last[node]=Tour.size();
}
void START(){
DFS(TOP);
}
int Query(int Start,int Top){
if(MOD==0){
int ans=Start;
for(int i=31;i>-1;i--){
if(ST[ans][i]>=Top)ans=ST[ans][i];
}
return ans;
}
int ans=Start;
for(int i=31;i>-1;i--){
if(ST[ans][i]<=Top)ans=ST[ans][i];
}
return ans;
}
void CMP(){
for(int i=0;i<Tour.size();i++){
if(first[Tour[i]]==-1)first[Tour[i]]=i;
last[Tour[i]]=i;
}
}
void print(){
/*for(int i=0;i<N;i++){
cout<<parent[i]<<" ";
}cout<<endl;*/
for(int i=0;i<Tour.size();i++){
cout<<Tour[i]<<" ";
}cout<<endl;
}
};
DSU *D1;
DSU *D2;
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 Q = S.size();
std::vector<int> A(Q);
D1=new DSU();D2=new DSU();
D1->init(N,0);
D2->init(N,1);
vector<pair<int,int> > order1;
vector<pair<int,int> > order2;
for(int i=0;i<X.size();i++){
if(X[i]<Y[i]){
order1.push_back(pii(X[i],Y[i]));
order2.push_back(pii(Y[i],X[i]));
}
else{
order1.push_back(pii(Y[i],X[i]));
order2.push_back(pii(X[i],Y[i]));
}
}
sort(order1.begin(),order1.end());
sort(order2.begin(),order2.end());
for(int i=order1.size()-1;i>-1;i--){
//cout<<order1[i].first<<" "<<order1[i].second<<endl;
D1->merge(order1[i].first,order1[i].second);
}D1->arrange();
D1->START();
//D1->CMP();
//D1->print();
for(int i=0;i<order2.size();i++){
D2->merge(order2[i].first,order2[i].second);
}
D2->arrange();
D2->START();
//D2->CMP();
//D2->print();
int Queries[Q][4];
for(int i=0;i<Q;i++){
Queries[i][0]=D1->first[D1->Query(S[i],L[i])];
Queries[i][1]=D1->last[D1->Query(S[i],L[i])];
Queries[i][2]=D2->first[D2->Query(E[i],R[i])];
Queries[i][3]=D2->last[D2->Query(E[i],R[i])];
//cout<<D2->Query(E[i],R[i])<<" ";
}//cout<<endl;
for (int i = 0; i < Q; ++i) {//cout<<i<<endl;
A[i] = 0;
for(int x=Queries[i][0];x<Queries[i][1];x++){
for(int y=Queries[i][2];y<Queries[i][3];y++){
if(D1->Tour[x]==D2->Tour[y])A[i]=1;
}
}
}
return A;
}
Compilation message
werewolf.cpp: In member function 'void DSU::DFS(int)':
werewolf.cpp:76:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<child[node].size();i++){
~^~~~~~~~~~~~~~~~~~~
werewolf.cpp: In member function 'void DSU::CMP()':
werewolf.cpp:100:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<Tour.size();i++){
~^~~~~~~~~~~~
werewolf.cpp: In member function 'void DSU::print()':
werewolf.cpp:109:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<Tour.size();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:127:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<X.size();i++){
~^~~~~~~~~
werewolf.cpp:146:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<order2.size();i++){
~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
264 ms |
329080 KB |
Output is correct |
| 2 |
Correct |
275 ms |
329176 KB |
Output is correct |
| 3 |
Correct |
272 ms |
329200 KB |
Output is correct |
| 4 |
Correct |
265 ms |
329320 KB |
Output is correct |
| 5 |
Correct |
262 ms |
329320 KB |
Output is correct |
| 6 |
Correct |
268 ms |
329428 KB |
Output is correct |
| 7 |
Correct |
274 ms |
329428 KB |
Output is correct |
| 8 |
Correct |
269 ms |
329428 KB |
Output is correct |
| 9 |
Correct |
280 ms |
329448 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
264 ms |
329080 KB |
Output is correct |
| 2 |
Correct |
275 ms |
329176 KB |
Output is correct |
| 3 |
Correct |
272 ms |
329200 KB |
Output is correct |
| 4 |
Correct |
265 ms |
329320 KB |
Output is correct |
| 5 |
Correct |
262 ms |
329320 KB |
Output is correct |
| 6 |
Correct |
268 ms |
329428 KB |
Output is correct |
| 7 |
Correct |
274 ms |
329428 KB |
Output is correct |
| 8 |
Correct |
269 ms |
329428 KB |
Output is correct |
| 9 |
Correct |
280 ms |
329448 KB |
Output is correct |
| 10 |
Execution timed out |
4058 ms |
329880 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4046 ms |
359700 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
264 ms |
329080 KB |
Output is correct |
| 2 |
Correct |
275 ms |
329176 KB |
Output is correct |
| 3 |
Correct |
272 ms |
329200 KB |
Output is correct |
| 4 |
Correct |
265 ms |
329320 KB |
Output is correct |
| 5 |
Correct |
262 ms |
329320 KB |
Output is correct |
| 6 |
Correct |
268 ms |
329428 KB |
Output is correct |
| 7 |
Correct |
274 ms |
329428 KB |
Output is correct |
| 8 |
Correct |
269 ms |
329428 KB |
Output is correct |
| 9 |
Correct |
280 ms |
329448 KB |
Output is correct |
| 10 |
Execution timed out |
4058 ms |
329880 KB |
Time limit exceeded |
| 11 |
Halted |
0 ms |
0 KB |
- |
