| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1039264 |
2024-07-30T15:45:20 Z |
vnm06 |
Werewolf (IOI18_werewolf) |
C++14 |
|
324 ms |
136136 KB |
#include<bits/stdc++.h>
#include "werewolf.h"
using namespace std;
int n, m, q;
int fenw[400005];
void update(int pos)
{
pos++;
while(pos<=n)
{
fenw[pos]++;
pos+=(pos&(-pos));
}
}
int query(int pos)
{
int res=0;
while(pos)
{
res+=fenw[pos];
pos-=(pos&(-pos));
}
return res;
}
int query(int le, int ri)
{
le++;
ri++;
return query(ri)-query(le-1);
}
int brcomp=0;
vector<int> compn[400005], gr[400005];
int nom_comp[400005], par[400005], par_comp[400005];
int new_nom[400005], tek_nom=1;
int be_id[400005], en_id[400005];
vector<int> spis_1[400005], spis_2[400005];
int tree_1[20][400005], tree_2[20][400005];
void build_tree_1()
{
for(int j=n-1; j>=0; j--) tree_1[0][j]=par[j];
for(int j=n-1; j>=0; j--)
{
if(par[j]!=-1) spis_1[par[j]].push_back(j);
}
for(int lvl=1; lvl<20; lvl++)
{
for(int v=0; v<n; v++)
{
if(tree_1[lvl-1][v]==-1) tree_1[lvl][v]=-1;
else tree_1[lvl][v]=tree_1[lvl-1][tree_1[lvl-1][v]];
}
}
}
void build_tree_2()
{
for(int j=n-1; j>=0; j--) tree_2[0][j]=par[j];
for(int j=n-1; j>=0; j--)
{
if(par[j]!=-1) spis_2[par[j]].push_back(j);
}
for(int lvl=1; lvl<20; lvl++)
{
for(int v=0; v<n; v++)
{
if(tree_2[lvl-1][v]==-1) tree_2[lvl][v]=-1;
else tree_2[lvl][v]=tree_2[lvl-1][tree_2[lvl-1][v]];
}
}
}
int be[400005], en[400005];
void renumerate(int v)
{
new_nom[v]=tek_nom;
be[v]=tek_nom;
tek_nom++;
int brs=spis_1[v].size();
for(int i=0; i<brs; i++)
{
renumerate(spis_1[v][i]);
}
en[v]=tek_nom-1;
}
int brv=0;
vector<int> Eut;
int fir[400005], las[400005];
void euler_tour(int v)
{
Eut.push_back(v);
fir[v]=brv;
las[v]=brv;
brv++;
int brs=spis_2[v].size();
for(int i=0; i<brs; i++)
{
euler_tour(spis_2[v][i]);
Eut.push_back(v);
las[v]=brv;
brv++;
}
}
int ans[400005];
vector<int> id_beg[400005], id_las[400005];
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)
{
q=S.size();
n=N;
m=X.size();
for(int i=0; i<m; i++)
{
gr[X[i]].push_back(Y[i]);
gr[Y[i]].push_back(X[i]);
}
memset(par, -1, sizeof(par));
for(int j=n-1; j>=0; j--)
{
compn[brcomp].push_back(j);
nom_comp[j]=brcomp;
par_comp[brcomp]=j;
brcomp++;
int brs=gr[j].size();
for(int i=0; i<brs; i++)
{
int nv=gr[j][i];
if(nv<j || nom_comp[j]==nom_comp[nv]) continue;
par[par_comp[nom_comp[nv]]]=j;
if(compn[nom_comp[j]].size()>compn[nom_comp[nv]].size())
{
int old_comp=nom_comp[nv];
for(int k=0; k<compn[old_comp].size(); k++)
{
int tv=compn[nom_comp[nv]][k];
nom_comp[tv]=nom_comp[j];
compn[nom_comp[j]].push_back(tv);
}
par_comp[nom_comp[j]]=j;
compn[old_comp].resize(0);
}
else
{
int old_comp=nom_comp[j];
for(int k=0; k<compn[old_comp].size(); k++)
{
int tv=compn[nom_comp[j]][k];
nom_comp[tv]=nom_comp[nv];
compn[nom_comp[nv]].push_back(tv);
}
par_comp[nom_comp[j]]=j;
compn[old_comp].resize(0);
}
}
}
build_tree_1();
for(int i=0; i<=brcomp+2; i++) {compn[i].resize(0); nom_comp[i]=0; par[i]=par_comp[i]=-1;}
brcomp=0;
for(int j=0; j<n; j++)
{
compn[brcomp].push_back(j);
nom_comp[j]=brcomp;
par_comp[brcomp]=j;
brcomp++;
int brs=gr[j].size();
for(int i=0; i<brs; i++)
{
int nv=gr[j][i];
if(nv>j || nom_comp[j]==nom_comp[nv]) continue;
par[par_comp[nom_comp[nv]]]=j;
if(compn[nom_comp[j]].size()>compn[nom_comp[nv]].size())
{
int old_comp=nom_comp[nv];
for(int k=0; k<compn[old_comp].size(); k++)
{
int tv=compn[nom_comp[nv]][k];
nom_comp[tv]=nom_comp[j];
compn[nom_comp[j]].push_back(tv);
}
par_comp[nom_comp[j]]=j;
compn[old_comp].resize(0);
}
else
{
int old_comp=nom_comp[j];
for(int k=0; k<compn[old_comp].size(); k++)
{
int tv=compn[nom_comp[j]][k];
nom_comp[tv]=nom_comp[nv];
compn[nom_comp[nv]].push_back(tv);
}
par_comp[nom_comp[j]]=j;
compn[old_comp].resize(0);
}
}
}
build_tree_2();
renumerate(0);
euler_tour(n-1);
for(int i=0; i<q; i++)
{
for(int lvl=19; lvl>=0; lvl--)
{
if(tree_1[lvl][S[i]]==-1) continue;
else if(tree_1[lvl][S[i]]>=L[i]) S[i]=tree_1[lvl][S[i]];
}
for(int lvl=19; lvl>=0; lvl--)
{
if(tree_2[lvl][E[i]]==-1) continue;
else if(tree_2[lvl][E[i]]<=R[i]) E[i]=tree_2[lvl][E[i]];
}
//cout<<S[i]<<' '<<E[i]<<endl;
if(fir[E[i]]) id_beg[fir[E[i]]-1].push_back(i);
id_las[las[E[i]]].push_back(i);
//cout<<fir[E[i]]<<" "<<las[E[i]]<<endl;
}
///for(int i=0; i<n; i++) //cout<<fir[i]<<" "<<las[i]<<" ";
//cout<<endl;
///for(int i=0; i<n; i++) //cout<<new_nom[i]<<" ";
//cout<<endl;
///for(int i=0; i<n; i++) //cout<<tree_2[0][i]<<" ";
//cout<<endl;
int totbr1=0, totbr2=0;
for(int i=0; i<Eut.size(); i++)
{
update(new_nom[Eut[i]]);
//cout<<new_nom[Eut[i]]<<" ";
for(int j=0; j<id_beg[i].size(); j++)
{
ans[id_beg[i][j]]-=query(be[S[id_beg[i][j]]], en[S[id_beg[i][j]]]);
totbr1++;
//cout<<id_beg[i][j]<<" "<<be[S[id_beg[i][j]]]<<" "<<en[S[id_beg[i][j]]]<<endl;
}
for(int j=0; j<id_las[i].size(); j++)
{
ans[id_las[i][j]]+=query(be[S[id_las[i][j]]], en[S[id_las[i][j]]]);
totbr2++;
//cout<<id_las[i][j]<<" "<<be[S[id_las[i][j]]]<<" "<<en[S[id_las[i][j]]]<<endl;
}
}
vector<int> A;
A.resize(q);
for(int i=0; i<q; i++) A[i]=bool(ans[i]);
return A;
}
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:149:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
149 | for(int k=0; k<compn[old_comp].size(); k++)
| ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:161:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
161 | for(int k=0; k<compn[old_comp].size(); k++)
| ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:192:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
192 | for(int k=0; k<compn[old_comp].size(); k++)
| ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:204:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
204 | for(int k=0; k<compn[old_comp].size(); k++)
| ~^~~~~~~~~~~~~~~~~~~~~~~
werewolf.cpp:245:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
245 | for(int i=0; i<Eut.size(); i++)
| ~^~~~~~~~~~~
werewolf.cpp:249:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
249 | for(int j=0; j<id_beg[i].size(); j++)
| ~^~~~~~~~~~~~~~~~~
werewolf.cpp:255:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
255 | for(int j=0; j<id_las[i].size(); j++)
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
58704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
58704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
324 ms |
136136 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
25 ms |
58704 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
