Submission #295307

#	Time	Username	Problem	Language	Result	Execution time	Memory
295307		muhammad_hokimiyon	Werewolf (IOI18_werewolf)	C++14	0 / 100	4070 ms	40716 KiB

werewolf

#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define ll long long
#define dl double long

const int maxn = 200200;

int n,m,q;
vector < int > ans;
int p1[maxn];
int p2[maxn];
int s1[maxn];
int s2[maxn];
vector < int > v[maxn],s,e,l,r;
vector < pair < int* , int > > bl,bl1;
vector < pair < int , int > > ask[maxn];

int get1( int x )
{
    return (p1[x] == x ? x : get1(p1[x]));
}

int get2( int x )
{
    return (p2[x] == x ? x : get2( p2[x] ));
}

void roll( int i )
{
    while( (int)bl.size() > i ){
        *bl.back().fi = bl.back().se;
        bl.pop_back();
    }
}

void roll1( int i )
{
    while( (int)bl1.size() > i ){
        *bl1.back().fi = bl1.back().se;
        bl1.pop_back();
    }
}

void meg1( int x , int y )
{
    int px = get1( x );
    int py = get1( y );
    if( px == py )return;
    if( s1[px] < s1[py] ){
        swap( px , py );
    }
    bl.push_back({ &p1[py] , p1[py] });
    bl.push_back({ &s1[px] , s1[px] });
    p1[py] = px;
    s1[px] += s1[py];
}

void meg2( int x , int y )
{
    int px = get2( x );
    int py = get2( y );
    if( px == py )return;
    if( s1[px] < s2[py] ){
        swap( px , py );
    }
    bl1.push_back({ &p2[py] , p2[py] });
    bl1.push_back({ &s2[px] , s2[px] });
    p2[py] = px;
    s2[px] += s2[py];
}

void solve( int l , int r )
{
    if( l > r )return;
    int m = (l + r) / 2;
    int l1 = (int)bl.size();
    int ll1 = (int)bl1.size();
    for( int i = l; i <= m; i++ ){
        for( auto x : v[i] ){
            if( x > m )continue;
            meg2( i , x );
        }
    }
    for( int i = m; i <= r; i++ ){
        for( auto x : v[i] ){
            if( x < m )continue;
            meg1( i , x );
        }
    }
    int l2 = (int)bl.size();
    int ll2 = (int)bl1.size();
    for( int i = m; i >= l; i-- ){
        for( auto x : v[i] ){
            if( x > i )meg1( x , i );
        }
        for( auto x : ask[i] ){
            if( x.fi < m )continue;
            int x1 = get1( s[x.se] );
            int x2 = get1( e[x.se] );
            int x5 = get2( e[x.se] );
            bool f = false;
            for( int j = i; j <= x.fi; j++ ){
                int x3 = get1( j );
                int x4 = get2( j );
                f |= (x1 == x3 && x5 == x2);
            }
            if( f ){
                ans[x.se] = 1;
            }else ans[x.se] = 0;
        }
    }
    roll( l1 );
    solve( m + 1 , r );
    roll1( ll1 );
    l1 = (int)bl.size();
    for( int i = m; i <= r; i++ ){
        for( auto x : v[i] ){
            if( x <= m )continue;
            meg1( i , x );
        }
    }
    solve( l , m - 1 );
    roll( l1 );
}

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)L.size();
    for( int i = 0; i < m; i++ ){
        int x = X[i] , y = Y[i];
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for( int i = 0; i < q; i++ ){
        ask[L[i]].push_back({ R[i] , i });
    }
    for( int i = 0; i < maxn; i++ ){
        p1[i] = p2[i] = i;
        s1[i] = s2[i] = 1;
    }
    ans.resize(q);
    s = S;
    e = E;
    l = L;
    r = R;
    solve( 0 , n - 1 );
    return ans;
}

Compilation message (stderr)

werewolf.cpp: In function 'void solve(int, int)':
werewolf.cpp:109:21: warning: unused variable 'x4' [-Wunused-variable]
  109 |                 int x4 = get2( j );
      |                     ^~
werewolf.cpp:95:9: warning: unused variable 'l2' [-Wunused-variable]
   95 |     int l2 = (int)bl.size();
      |         ^~
werewolf.cpp:96:9: warning: unused variable 'll2' [-Wunused-variable]
   96 |     int ll2 = (int)bl1.size();
      |         ^~~

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