Submission #603085

#	Time	Username	Problem	Language	Result	Execution time	Memory
603085		achibasadzishvili	Werewolf (IOI18_werewolf)	C++14	100 / 100	962 ms	150424 KiB

werewolf

#include<bits/stdc++.h>
#include "werewolf.h"
#define ll int
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define maxn 400005
using namespace std;
ll m,n,p[maxn],in1[maxn],out1[maxn],in2[maxn],out2[maxn],ans[maxn];
ll tout1[maxn],tout2[maxn],tin1[maxn],tin2[maxn],s[maxn],t[maxn],l[maxn],r[maxn];
ll P1[200005][19],P2[200005][19],q,was[maxn],pown = 1;
vector<ll>v[maxn],ne[maxn],ol[maxn],be[maxn],ed[maxn];
vector<pair<ll,ll> >g;
ll tt[6000005];
ll timer = 0;
ll find(ll x){
	if(p[x] == x)return x;
	return p[x] = find(p[x]);
}
void join(ll x,ll y){
	x = find(x);
	y = find(y);
	if(x == y)return;
    if(y > x)swap(x,y);
	p[y] = x;
}
void join1(ll x,ll y){
	x = find(x);
	y = find(y);
	if(x == y)return;
	if(y < x)swap(x , y);
	p[y] = x;
}
void dfs(ll x, ll par){
    timer++;
    in1[x] = timer;
    tin1[timer] = x;
    
    P1[x][0] = par;
    for(int i=1;i<=18;i++)
        P1[x][i] = P1[P1[x][i-1]][i-1];
    
    for(int i=0; i<ne[x].size(); i++)
        if(ne[x][i] != par)
            dfs(ne[x][i],x);
    timer++;
    out1[x] = timer;
    tout1[timer] = x;
}
void dfs1(ll x,ll par){
    timer++;
    in2[x] = timer;
    tin2[timer] = x;
    P2[x][0] = par;
    for(int i=1;i<=18;i++)
        P2[x][i] = P2[P2[x][i-1]][i-1];
        
    for(int i=0; i<ol[x].size(); i++)
        if(ol[x][i] != par)
            dfs1(ol[x][i],x);
    timer++;
    out2[x] = timer;
    tout2[timer] = x;
}
ll bigne(ll x,ll y){
    for(int i=18; i>=0; i--)
        if(P1[x][i])
            if(P1[x][i] <= y)
                x = P1[x][i];
    return x;
}
ll bigol(ll x,ll y){
    for(int i=18; i>=0; i--)
        if(P2[x][i])
            if(P2[x][i] >= y)
                x = P2[x][i];
    return x;
}
void upd(ll x){
	if(!x)return;
	tt[x] = tt[2 * x] + tt[2 * x + 1];
	upd(x / 2);
}
ll cnt(ll x,ll L,ll R,ll l1,ll r1){
	if(L > r1 || R < l1)return 0;
	if(L >= l1 && R <= r1)return tt[x];
	ll k1 = cnt(2 * x,L , (L + R) / 2 , l1 , r1);
	ll k2 = cnt(2 * x + 1,(L + R) / 2 + 1 , R , l1 , r1);
	return k1 + k2;
}

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) {
    n = N;
    while(pown <= 2 * n)pown *= 2;
    m = X.size();
    
    for(int i=1; i<=m; i++){
        ll x,y;
        x = X[i - 1];
        y = Y[i - 1];
		x++;
		y++;
        v[x].pb(y);
        v[y].pb(x);
        g.pb(mp(max(x,y) , min(x,y)));
    }
    
    
  int Q = S.size();
    q = Q;
    for(int i=1; i<=q; i++){
        s[i] = S[i - 1];
        t[i] = E[i - 1];
        l[i] = L[i - 1];
        r[i] = R[i - 1];
		s[i]++;
		t[i]++;
		l[i]++;
		r[i]++;
    }
    
    sort(g.begin(),g.end());
    
    for(int i=1; i<=n; i++){
        p[i] = i;
    }
    
    for(int i=0; i<g.size(); i++){
        ll x,y;
        x = g[i].f;
        y = g[i].s;
        x = find(x);
        y = find(y);
        if(x != y){
            join(x,y);
            ne[x].pb(y);
            ne[y].pb(x);
        }
    }
    
	for(int i=0; i<g.size(); i++){
		swap(g[i].f , g[i].s);
	}
	
	sort(g.begin() , g.end());
	
	reverse(g.begin() , g.end());
    
    for(int i=1; i<=n; i++){
        p[i] = i;
    }
	
    for(int i=0; i<g.size(); i++){
        ll x,y;
        x = g[i].f;
        y = g[i].s;
        x = find(x);
        y = find(y);
        if(x != y){
            join1(x,y);
            ol[x].pb(y);
            ol[y].pb(x);
        }
    }
    
    dfs(n,0);
    
    timer = 0;
    
    dfs1(1,0);
    
    for(int i=1; i<=q; i++){
        s[i] = bigol(s[i] , l[i]);
        t[i] = bigne(t[i] , r[i]);
		be[in2[s[i]]].pb(i);
		ed[out2[s[i]]].pb(i);
	}
    
	
	for(int i=1; i<=2 * n; i++){
		for(int j=0; j<be[i].size(); j++)
			was[be[i][j]] = cnt(1,1,pown,in1[t[be[i][j]]] , out1[t[be[i][j]]]);
		if(tin2[i] != 0){
			tt[pown + in1[tin2[i]] - 1]++;
			upd((pown + in1[tin2[i]] - 1) / 2);
		}
		
		for(int j=0; j < ed[i].size(); j++){
			ll now = cnt(1,1,pown,in1[t[ed[i][j]]] , out1[t[ed[i][j]]] );
			if(now > was[ed[i][j]])
				ans[ed[i][j]] = 1;
		}
	}

  std::vector<int> A(Q);
  for (int i = 0; i < Q; ++i)
    A[i] = ans[i + 1];
  return A;
}

Compilation message (stderr)

werewolf.cpp: In function 'void dfs(int, int)':
werewolf.cpp:44:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for(int i=0; i<ne[x].size(); i++)
      |                  ~^~~~~~~~~~~~~
werewolf.cpp: In function 'void dfs1(int, int)':
werewolf.cpp:59:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i=0; i<ol[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:131:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for(int i=0; i<g.size(); i++){
      |                  ~^~~~~~~~~
werewolf.cpp:144:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |  for(int i=0; i<g.size(); i++){
      |               ~^~~~~~~~~
werewolf.cpp:156:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for(int i=0; i<g.size(); i++){
      |                  ~^~~~~~~~~
werewolf.cpp:184:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  184 |   for(int j=0; j<be[i].size(); j++)
      |                ~^~~~~~~~~~~~~
werewolf.cpp:191:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |   for(int j=0; j < ed[i].size(); j++){
      |                ~~^~~~~~~~~~~~~~

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