oj.uz

Submission #298069

# Submission time Handle Problem Language Result Execution time Memory
298069 2020-09-12T10:56:06 Z muhammad_hokimiyon Werewolf (IOI18_werewolf) C++14
100 / 100
 1860 ms 142132 KB 
#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;
int tim;
int tin1[maxn];
int tout1[maxn];
int tin2[maxn];
int tout2[maxn];
int p[maxn];
int o1[maxn];
int o2[maxn];
int d1[maxn][25];
int d2[maxn][25];
vector < int > g[maxn];
vector < int > v[maxn],t[4 * maxn];
vector < pair < int , int > > gg[maxn];

void build( int x , int l , int r )
{
    if( l == r ){
        t[x].push_back( tin1[o2[l]] );
        return;
    }
    int m = (l + r) / 2;
    build( x + x , l , m );
    build( x + x + 1 , m + 1 , r );
    int i = 0 , j = 0;
    while( i < (int)t[x + x].size() && j < (int)t[x + x + 1].size() ){
        if( t[x + x][i] < t[x + x + 1][j] ){
            t[x].push_back(t[x + x][i++]);
        }else t[x].push_back(t[x + x + 1][j++]);
    }
    while( j < (int)t[x + x + 1].size() ){
        t[x].push_back(t[x + x + 1][j++]);
    }
    while( i < (int)t[x + x].size() ){
        t[x].push_back(t[x + x][i++]);
    }
}

int get1( int x , int l , int r , int tl , int tr , int tl1 , int tr1 )
{
    if( tl > tr )return 0;
    if( l == tl && r == tr ){
        int y = (int)(lower_bound( t[x].begin() , t[x].end() , tl1 ) - t[x].begin());
        if( y != (int)t[x].size() && t[x][y] <= tr1 )return 1;
        return 0;
    }
    int m = (l + r) / 2;
    return ( get1( x + x , l , m , tl , min( tr , m ) , tl1 , tr1 ) |
               get1( x + x + 1 , m + 1 , r , max( tl , m + 1 ) , tr , tl1 , tr1 ) );
}

int get( int x )
{
    return (p[x] == x ? x : p[x] = get(p[x]));
}

void meg( int x , int y )
{
    int px = get(x);
    int py = get(y);
    if( px == py )return;
    p[px] = py;
    g[py].push_back(px);
    g[px].push_back(py);
}

void dfs( int x , int p )
{
    d1[x][0] = p;
    for( int i = 1; i < 25; i++ ){
        d1[x][i] = d1[d1[x][i - 1]][i - 1];
    }
    tin1[x] = ++tim;
    o1[tim] = x;
    for( auto y : g[x] ){
        if( y == p )continue;
        dfs( y , x );
    }
    tout1[x] = tim;
}

int ff( int x , int y )
{
    for( int i = 24; i >= 0; i-- ){
        if( d2[x][i] <= y ){
            x = d2[x][i];
        }
    }
    return x;
}

int ff1( int x , int y )
{
    for( int i = 24; i >= 0; i-- ){
        if( d1[x][i] >= y ){
            x = d1[x][i];
        }
    }
    return 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();
    for( int i = 1; i <= n; i++ ){
        p[i] = i;
    }
    for( int i = 0; i < m; i++ ){
        v[X[i]].push_back(Y[i]);
        v[Y[i]].push_back(X[i]);
    }
    for( int i = 0; i < n; i++ ){
        for( auto x : v[i] ){
            if( x > i )continue;
            meg( x , i );
        }
    }
    dfs( n - 1 , n - 1 );
    for( int i = 0; i <= n; i++ ){
        tin2[i] = tin1[i];
        tout2[i] = tout1[i];
        o2[i] = o1[i];
        g[i].clear();
        p[i] = i;
        for( int j = 0; j < 25; j++ ){
            d2[i][j] = d1[i][j];
        }
    }
    tim = 0;
    for( int i = n - 1; i >= 0; i-- ){
        for( auto x : v[i] ){
            if( x < i )continue;
            meg( x , i );
        }
    }
    dfs( 0 , 0 );
    for( int i = 0; i < q; i++ ){
        gg[R[i]].push_back({L[i] , i});
    }
    build( 1 , 1 , n );
    vector < int > ans(q , -1);
    for( int i = 0; i < n; i++ ){
        for( auto x : gg[i] ){
            int yy = ff( E[x.se] , i );
            int y = ff1( S[x.se] , x.fi );
            ans[x.se] = get1( 1 , 1 , n , tin2[yy] , tout2[yy] , tin1[y] , tout1[y] );
        }
    }
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33280 KB Output is correct
2 Correct 28 ms 33440 KB Output is correct
3 Correct 28 ms 33280 KB Output is correct
4 Correct 28 ms 33280 KB Output is correct
5 Correct 28 ms 33280 KB Output is correct
6 Correct 27 ms 33280 KB Output is correct
7 Correct 29 ms 33280 KB Output is correct
8 Correct 31 ms 33280 KB Output is correct
9 Correct 27 ms 33280 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33280 KB Output is correct
2 Correct 28 ms 33440 KB Output is correct
3 Correct 28 ms 33280 KB Output is correct
4 Correct 28 ms 33280 KB Output is correct
5 Correct 28 ms 33280 KB Output is correct
6 Correct 27 ms 33280 KB Output is correct
7 Correct 29 ms 33280 KB Output is correct
8 Correct 31 ms 33280 KB Output is correct
9 Correct 27 ms 33280 KB Output is correct
10 Correct 38 ms 34812 KB Output is correct
11 Correct 38 ms 34688 KB Output is correct
12 Correct 37 ms 34688 KB Output is correct
13 Correct 43 ms 34944 KB Output is correct
14 Correct 38 ms 34816 KB Output is correct
15 Correct 39 ms 34808 KB Output is correct

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1503 ms 131692 KB Output is correct
2 Correct 1532 ms 135148 KB Output is correct
3 Correct 1343 ms 132844 KB Output is correct
4 Correct 1318 ms 131948 KB Output is correct
5 Correct 1350 ms 131824 KB Output is correct
6 Correct 1449 ms 131768 KB Output is correct
7 Correct 1300 ms 130392 KB Output is correct
8 Correct 1336 ms 135140 KB Output is correct
9 Correct 1062 ms 133228 KB Output is correct
10 Correct 915 ms 130016 KB Output is correct
11 Correct 1075 ms 130412 KB Output is correct
12 Correct 1211 ms 132076 KB Output is correct
13 Correct 1519 ms 136300 KB Output is correct
14 Correct 1433 ms 136308 KB Output is correct
15 Correct 1497 ms 136300 KB Output is correct
16 Correct 1429 ms 136548 KB Output is correct
17 Correct 1293 ms 130392 KB Output is correct

Subtask #4
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 33280 KB Output is correct
2 Correct 28 ms 33440 KB Output is correct
3 Correct 28 ms 33280 KB Output is correct
4 Correct 28 ms 33280 KB Output is correct
5 Correct 28 ms 33280 KB Output is correct
6 Correct 27 ms 33280 KB Output is correct
7 Correct 29 ms 33280 KB Output is correct
8 Correct 31 ms 33280 KB Output is correct
9 Correct 27 ms 33280 KB Output is correct
10 Correct 38 ms 34812 KB Output is correct
11 Correct 38 ms 34688 KB Output is correct
12 Correct 37 ms 34688 KB Output is correct
13 Correct 43 ms 34944 KB Output is correct
14 Correct 38 ms 34816 KB Output is correct
15 Correct 39 ms 34808 KB Output is correct
16 Correct 1503 ms 131692 KB Output is correct
17 Correct 1532 ms 135148 KB Output is correct
18 Correct 1343 ms 132844 KB Output is correct
19 Correct 1318 ms 131948 KB Output is correct
20 Correct 1350 ms 131824 KB Output is correct
21 Correct 1449 ms 131768 KB Output is correct
22 Correct 1300 ms 130392 KB Output is correct
23 Correct 1336 ms 135140 KB Output is correct
24 Correct 1062 ms 133228 KB Output is correct
25 Correct 915 ms 130016 KB Output is correct
26 Correct 1075 ms 130412 KB Output is correct
27 Correct 1211 ms 132076 KB Output is correct
28 Correct 1519 ms 136300 KB Output is correct
29 Correct 1433 ms 136308 KB Output is correct
30 Correct 1497 ms 136300 KB Output is correct
31 Correct 1429 ms 136548 KB Output is correct
32 Correct 1293 ms 130392 KB Output is correct
33 Correct 1606 ms 132972 KB Output is correct
34 Correct 493 ms 55288 KB Output is correct
35 Correct 1860 ms 135220 KB Output is correct
36 Correct 1628 ms 132204 KB Output is correct
37 Correct 1804 ms 134640 KB Output is correct
38 Correct 1677 ms 132844 KB Output is correct
39 Correct 1459 ms 141676 KB Output is correct
40 Correct 1732 ms 136680 KB Output is correct
41 Correct 1441 ms 134252 KB Output is correct
42 Correct 1227 ms 132832 KB Output is correct
43 Correct 1819 ms 137872 KB Output is correct
44 Correct 1606 ms 134420 KB Output is correct
45 Correct 1188 ms 142132 KB Output is correct
46 Correct 1218 ms 141932 KB Output is correct
47 Correct 1514 ms 136428 KB Output is correct
48 Correct 1506 ms 136300 KB Output is correct
49 Correct 1469 ms 136348 KB Output is correct
50 Correct 1482 ms 136428 KB Output is correct
51 Correct 1639 ms 136832 KB Output is correct
52 Correct 1654 ms 136812 KB Output is correct