| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 100366 |
2019-03-10T15:53:34 Z |
MvC |
Werewolf (IOI18_werewolf) |
C++11 |
|
797 ms |
525312 KB |
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
using namespace std;
int n,i,j,t,m,q,l[nmax],r[nmax],s[nmax],e[nmax],id[nmax],bit[nmax],x,y,st,dr,rs,mid,lf[nmax],rg[nmax];
vector<int>g[nmax],vl[nmax],vr[nmax];
void upd(int i)
{
for(;i<=n;i+=i&(-i))bit[i]++;
}
int qry(int i)
{
if(!i)return 0;
int sm=0;
for(;i>=1;i-=i&(-i))sm+=bit[i];
return sm;
}
void dfs(int x,int p)
{
id[x]=id[p]+1;
for(int i=0;i<g[x].size();i++)
{
if(g[x][i]==p)continue;
dfs(g[x][i],x);
}
}
vector<int>check_validity(int N,vector<int>X,vector<int>Y,vector<int>S,vector<int>E,vector<int>L,vector<int>R)
{
n=N,m=(int)X.size(),q=(int)S.size();
vector<int>ans;
for(i=0;i<m;i++)
{
x=X[i],y=Y[i];
x++,y++;
g[x].pb(y);
g[y].pb(x);
}
for(i=1;i<=n;i++)
{
if(g[i].size()==1)
{
x=i;
break;
}
}
dfs(x,x);
for(i=1;i<=q;i++)
{
s[i]=S[i-1],e[i]=E[i-1],l[i]=L[i-1],r[i]=R[i-1];
s[i]++,e[i]++,l[i]++,r[i]++;
s[i]=id[s[i]],e[i]=id[e[i]];
vl[l[i]].pb(i);
vr[r[i]].pb(i);
}
for(i=n;i>=1;i--)
{
upd(id[i]);
for(j=0;j<vl[i].size();j++)
{
t=vl[i][j];
if(s[t]<e[t])
{
st=s[t],dr=e[t],rs=-1;
x=qry(s[t]-1);
while(st<=dr)
{
mid=(st+dr)/2;
if(qry(mid)-x==mid-s[t]+1)rs=mid,st=mid+1;
else dr=mid-1;
}
}
else
{
st=e[t],dr=s[t],rs=-1;
x=qry(s[t]);
while(st<=dr)
{
mid=(st+dr)/2;
if(x-qry(mid-1)==s[t]-mid+1)rs=mid,dr=mid-1;
else st=mid+1;
}
}
lf[t]=rs;
}
}
memset(bit,0,sizeof(bit));
for(i=1;i<=n;i++)
{
upd(id[i]);
for(j=0;j<vr[i].size();j++)
{
t=vr[i][j];
if(s[t]<e[t])
{
st=s[t],dr=e[t],rs=-1;
x=qry(e[t]);
while(st<=dr)
{
mid=(st+dr)/2;
if(x-qry(mid-1)==e[t]-mid+1)rs=mid,dr=mid-1;
else st=mid+1;
}
}
else
{
st=e[t],dr=s[t],rs=-1;
x=qry(e[t]-1);
while(st<=dr)
{
mid=(st+dr)/2;
if(qry(mid)-x==mid-e[t]+1)rs=mid,st=mid+1;
else dr=mid-1;
}
}
rg[t]=rs;
}
}
for(i=1;i<=q;i++)
{
if(s[i]<e[i])
{
if(lf[i]==-1 || rg[i]==-1 || lf[i]<rg[i])ans.pb(0);
else ans.pb(1);
}
else
{
if(lf[i]==-1 || rg[i]==-1 || lf[i]>rg[i])ans.pb(0);
else ans.pb(1);
}
}
return ans;
}
/*int main()
{
//freopen("sol.in","r",stdin);
//freopen("sol.out","w",stdout);
ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
cin>>n>>m>>q;
while(m--)
{
cin>>x>>y;
x++,y++;
g[x].pb(y);
g[y].pb(x);
}
for(i=1;i<=n;i++)
{
if(g[i].size()==1)
{
x=i;
break;
}
}
dfs(x,x);
for(i=1;i<=q;i++)
{
cin>>s[i]>>e[i]>>l[i]>>r[i];
s[i]++,e[i]++,l[i]++,r[i]++;
s[i]=id[s[i]],e[i]=id[e[i]];
vl[l[i]].pb(i);
vr[r[i]].pb(i);
}
for(i=n;i>=1;i--)
{
upd(id[i]);
for(j=0;j<vl[i].size();j++)
{
t=vl[i][j];
if(s[t]<e[t])
{
st=s[t],dr=e[t],rs=-1;
x=qry(s[t]-1);
while(st<=dr)
{
mid=(st+dr)/2;
if(qry(mid)-x==mid-s[t]+1)rs=mid,st=mid+1;
else dr=mid-1;
}
}
else
{
st=e[t],dr=s[t],rs=-1;
x=qry(s[t]);
while(st<=dr)
{
mid=(st+dr)/2;
if(x-qry(mid-1)==s[t]-mid+1)rs=mid,dr=mid-1;
else st=mid+1;
}
}
lf[t]=rs;
}
}
memset(bit,0,sizeof(bit));
for(i=1;i<=n;i++)
{
upd(id[i]);
for(j=0;j<vr[i].size();j++)
{
t=vr[i][j];
if(s[t]<e[t])
{
st=s[t],dr=e[t],rs=-1;
x=qry(e[t]);
while(st<=dr)
{
mid=(st+dr)/2;
if(x-qry(mid-1)==e[t]-mid+1)rs=mid,dr=mid-1;
else st=mid+1;
}
}
else
{
st=e[t],dr=s[t],rs=-1;
x=qry(e[t]-1);
while(st<=dr)
{
mid=(st+dr)/2;
if(qry(mid)-x==mid-e[t]+1)rs=mid,st=mid+1;
else dr=mid-1;
}
}
rg[t]=rs;
}
}
for(i=1;i<=q;i++)
{
if(s[i]<e[i])
{
if(lf[i]==-1 || rg[i]==-1 || lf[i]<rg[i])cout<<0<<" ";
else cout<<1<<" ";
}
else
{
if(lf[i]==-1 || rg[i]==-1 || lf[i]>rg[i])cout<<0<<" ";
else cout<<1<<" ";
}
cout<<lf[i]<<" "<<rg[i]<<endl;
}
cout<<endl;
return 0;
}
/*
8 7 1
0 2
2 4
4 1
1 6
6 5
5 3
3 7
4 7 3 7
*/
Compilation message
werewolf.cpp:256:1: warning: "/*" within comment [-Wcomment]
/*
werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:34:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[x].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:71:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<vl[i].size();j++)
~^~~~~~~~~~~~~
werewolf.cpp:103:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<vr[i].size();j++)
~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
536 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
536 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
699 ms |
49984 KB |
Output is correct |
| 2 |
Correct |
675 ms |
58188 KB |
Output is correct |
| 3 |
Correct |
654 ms |
58196 KB |
Output is correct |
| 4 |
Correct |
728 ms |
58228 KB |
Output is correct |
| 5 |
Correct |
717 ms |
58144 KB |
Output is correct |
| 6 |
Correct |
685 ms |
58108 KB |
Output is correct |
| 7 |
Correct |
633 ms |
56008 KB |
Output is correct |
| 8 |
Correct |
659 ms |
58172 KB |
Output is correct |
| 9 |
Correct |
521 ms |
57204 KB |
Output is correct |
| 10 |
Correct |
587 ms |
56828 KB |
Output is correct |
| 11 |
Correct |
593 ms |
57076 KB |
Output is correct |
| 12 |
Correct |
597 ms |
57828 KB |
Output is correct |
| 13 |
Correct |
728 ms |
58204 KB |
Output is correct |
| 14 |
Correct |
797 ms |
58360 KB |
Output is correct |
| 15 |
Correct |
716 ms |
58132 KB |
Output is correct |
| 16 |
Correct |
714 ms |
58140 KB |
Output is correct |
| 17 |
Correct |
683 ms |
56048 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
536 ms |
525312 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
