Submission #121495

#	Time	Username	Problem	Language	Result	Execution time	Memory
121495		TadijaSebez	Werewolf (IOI18_werewolf)	C++11	100 / 100	1377 ms	117480 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=200050;
const int L=19;
struct DSU
{
	int p[N];
	void init(){ for(int i=0;i<N;i++) p[i]=i;}
	DSU(){ init();}
	int Find(int x){ return p[x]==x?x:p[x]=Find(p[x]);}
	void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
struct BIT
{
	int sum[N];
	void init(){ for(int i=0;i<N;i++) sum[i]=0;}
	BIT(){ init();}
	void Add(int i, int f){ for(;i<N;i+=i&-i) sum[i]+=f;}
	int Get(int i){ int ret=0;for(;i;i-=i&-i) ret+=sum[i];return ret;}
	int Get(int l, int r){ return Get(r)-Get(l-1);}
} BT;
struct Tree
{
	vector<int> E[N];
	int par[N][L],dep[N],root,nod[N],lid[N],rid[N],tid;
	Tree(){}
	void AddEdge(int u, int v){ E[u].pb(v);E[v].pb(u);}
	void SetRoot(int u){ root=u;}
	void DFS(int u, int p)
	{
		lid[u]=++tid;
		nod[tid]=u;
		par[u][0]=p;
		dep[u]=dep[p]+1;
		//printf("%i ",u);
		for(int i=1;i<L;i++) par[u][i]=par[par[u][i-1]][i-1];
		for(int v:E[u]) if(v!=p) DFS(v,u);
		//printf("%i ",u);
		rid[u]=tid;
	}
	void DFS(){ DFS(root,0);}//printf("\n");}
	int UpLo(int u, int x)
	{
		for(int i=L-1;~i;i--) if(par[u][i]!=0 && par[u][i]<=x) u=par[u][i];
		return u;
	}
	int UpHi(int u, int x)
	{
		for(int i=L-1;~i;i--) if(par[u][i]!=0 && par[u][i]>=x) u=par[u][i];
		return u;
	}
} Lree,Rree;
struct Query
{
	int l,r,mul,id;
	Query(int b=0, int c=0, int e=0, int f=0){ l=b,r=c,mul=e,id=f;}
};
int sol[N];
struct QuerySolver
{
    int a[N],b[N],id[N],n;
	vector<Query> Qs[N];
	QuerySolver(){}
	void init(int v[], int u[], int sz)
	{
		n=sz;
		for(int i=1;i<=n;i++) a[i]=v[i],b[i]=u[i];
		for(int i=1;i<=n;i++) id[b[i]]=i;
	}
	void AddQuery(int s, int e, int l, int r, int idex)
	{
		Qs[s-1].pb(Query(l,r,-1,idex));
		Qs[e].pb(Query(l,r,1,idex));
	}
	void Solve()
	{
		for(int i=1;i<=n;i++)
		{
			BT.Add(id[a[i]],1);
			for(Query my:Qs[i])
			{
                sol[my.id]+=my.mul*BT.Get(my.l,my.r);
			}
		}
	}
} Solver;
vector<int> E[N];
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 m=x.size(),q=s.size();
	for(int i=0;i<m;i++) x[i]++,y[i]++;
	for(int i=0;i<q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
	for(int i=0;i<m;i++) x[i]++,y[i]++;
	for(int i=0;i<q;i++) s[i]++,e[i]++,l[i]++,r[i]++;
	n+=2;
	for(int i=2;i<=n;i++) E[1].pb(i);
	for(int i=1;i<n;i++) E[n].pb(i);
	for(int i=0;i<m;i++) E[x[i]].pb(y[i]),E[y[i]].pb(x[i]);
	DS.init();
	for(int i=1;i<=n;i++) for(int j:E[i]) if(j<i && DS.Find(i)!=DS.Find(j)) Lree.AddEdge(DS.Find(j),i),DS.Union(j,i);
	DS.init();
	for(int i=n;i>=1;i--) for(int j:E[i]) if(j>i && DS.Find(i)!=DS.Find(j)) Rree.AddEdge(DS.Find(j),i),DS.Union(j,i);
	Lree.SetRoot(n);Rree.SetRoot(1);
	Lree.DFS();Rree.DFS();
	//for(int i=1;i<=n;i++) printf("%i ",Lree.nod[i]);printf("\n");
	//for(int i=1;i<=n;i++) printf("%i ",Rree.nod[i]);printf("\n");
	BT.init();
	Solver.init(Lree.nod,Rree.nod,n);
	for(int i=0;i<q;i++)
	{
        int u=Rree.UpHi(s[i],l[i]);
        int v=Lree.UpLo(e[i],r[i]);
        Solver.AddQuery(Lree.lid[v],Lree.rid[v],Rree.lid[u],Rree.rid[u],i);
	}
	vector<int> ret;
	Solver.Solve();
	for(int i=0;i<q;i++) ret.pb(sol[i]>0);
	return ret;
}
/*int read_int(){ int x;scanf("%i",&x);return x;}
int main() {
  int N = read_int();
  int M = read_int();
  int Q = read_int();
  std::vector<int> X(M), Y(M), S(Q), E(Q), L(Q), R(Q);
  for (int j = 0; j < M; ++j) {
    X[j] = read_int();
    Y[j] = read_int();
  }
  for (int i = 0; i < Q; ++i) {
    S[i] = read_int();
    E[i] = read_int();
    L[i] = read_int();
    R[i] = read_int();
  }

  std::vector<int> A = check_validity(N, X, Y, S, E, L, R);
  for (size_t i = 0; i < A.size(); ++i) {
    printf("%d\n", A[i]);
  }
  return 0;
}*/

• Subtask 1: 7 / 7
• Subtask 2: 8 / 8
• Subtask 3: 34 / 34
• Subtask 4: 51 / 51