oj.uz

Submission #948873

# Submission time Handle Problem Language Result Execution time Memory
948873 2024-03-18T15:45:14 Z LucaIlie Inside information (BOI21_servers) C++17
0 / 100
 3500 ms 32280 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1.2e5;
const int MAX_Q = 1.2e5;

struct edge {
    int u, v, t;

    int other( int x ) {
        return u ^ v ^ x;
    }
};

struct query {
    char type;
    int u, v, t, ans;
};


struct FRECV {
    int f[MAX_N + 1];
    vector<int> ch;

    void init() {
        for ( int i = 0; i <= MAX_N; i++ )
            f[i] = MAX_N + MAX_Q + 1;
    }
    void clear() {
        for ( int i: ch )
            f[i] = MAX_N + MAX_Q + 1;
        ch.clear();
    }

    void update( int i, int x ) {
        f[i] = x;
        ch.push_back( i );
    }

    int qry( int x ){
        return f[x];
    }
};

struct AIB {
    int aib[MAX_N + MAX_Q];
    vector<int> ch;

    void clear() {
        for ( int i: ch )
            aib[i] = 0;
        ch.clear();
    }

    void update( int i, int x ) {
        while ( i <= MAX_N + MAX_Q ) {
            aib[i] += x;
            ch.push_back( i );
            i += (i & -i);
        }
    }

    int query( int i ) {
        int s = 0;

        while ( i > 0 ) {
            s += aib[i];
            i -= (i & -i);
        }

        return s;
    }
};

edge edges[MAX_N];
query queries[MAX_Q];
vector<int> adj[MAX_N + 1], queriesQ[MAX_N + 1], queriesC[MAX_N + 1];

bool isCentroid[MAX_N + 1];
int sizee[MAX_N + 1];

void calcSizes( int u, int p ) {
    sizee[u] = 1;
    for ( int e: adj[u] ) {
        int v = edges[e].other( u );
        if ( v == p || isCentroid[v] )
            continue;
        calcSizes( v, u );
        sizee[u] += sizee[v];
    }
}

int sz, centroid;
void findCentroid( int u, int p ) {
    int maxSizee = 0;
    for ( int e: adj[u] ) {
        int v = edges[e].other( u );
        if ( v == p || isCentroid[v] )
            continue;
        findCentroid( v, u );
        maxSizee = max( maxSizee, sizee[v] );
    }
    maxSizee = max( maxSizee, sz - sizee[u] );

    if ( maxSizee <= sz / 2 )
        centroid = u;
}

vector<pair<int, int>> incc;
vector<int> decc;

void calcIncreasing( int u, int p, int t ) {
    incc.push_back( { u, t } );
    for ( int e: adj[u] ) {
        int v = edges[e].other( u ), s = edges[e].t;
        if ( v == p || isCentroid[v] || t > s )
            continue;
        calcIncreasing( v, u, s );
    }
}

void calcDecreasing( int u, int p, int t ) {
    decc.push_back( u );
    for ( int e: adj[u] ) {
        int v = edges[e].other( u ), s = edges[e].t;
        if ( v == p || isCentroid[v] || t < s )
            continue;
        calcDecreasing( v, u, s );
    }
}

FRECV timee;
AIB lowerTimee;

void decomp( int r ) {
    calcSizes( r, 0 );
    sz = sizee[r];
    findCentroid( r, 0 );
    int c = centroid;
    isCentroid[c] = true;

    sort( adj[c].begin(), adj[c].end(), []( int e, int f ) {
        return edges[e].t > edges[f].t;
    } );

    timee.clear();
    lowerTimee.clear();
    timee.update( c, 1 );
    lowerTimee.update( 1, 1 );
    for ( int e: adj[c] ) {
        int v = edges[e].other( c );
        if ( isCentroid[v] )
            continue;

        incc.clear();
        decc.clear();
        calcIncreasing( v, c, edges[e].t );
        calcDecreasing( v, c, edges[e].t );

        for ( int u: decc ) {
            for ( int q: queriesQ[u] )
                queries[q].ans |= (timee.qry( queries[q].u ) <= queries[q].t);
            for ( int q: queriesC[u] )
                queries[q].ans += lowerTimee.query( queries[q].t );
        }

        for ( auto p: incc ) {
            int u = p.first, t = p.second;
            timee.update( u, t );
            lowerTimee.update( t, 1 );
        }
    }
    for ( int q: queriesQ[c] )
        queries[q].ans |= (timee.qry( queries[q].u ) <= queries[q].t);
    for ( int q: queriesC[c] )
        queries[q].ans += lowerTimee.query( queries[q].t );

    for ( int e: adj[c] ) {
        int v = edges[e].other( c );
        if ( !isCentroid[v] )
            decomp( v );
    }
}

int main() {
    int n, q;

    cin >> n >> q;

    for ( int t = 1, i = 0, j = 0; t <= n + q - 1; t++ ) {
        char ch;

        cin >> ch;
        if ( ch == 'S' ) {
            cin >> edges[i].u >> edges[i].v;
            adj[edges[i].u].push_back( i );
            adj[edges[i].v].push_back( i );
            edges[i].t = t;
            i++;
        } else {
            queries[j].type = ch;
            if ( ch == 'Q' ) {
                cin >> queries[j].u >> queries[j].v;
                queriesQ[queries[j].v].push_back( j );
            } else {
                cin >> queries[j].v;
                queriesC[queries[j].v].push_back( j );
            }
            queries[j].t = t;
            j++;
        }
    }

    timee.init();

    for ( int i = 1; i <= n; i++ )
        isCentroid[i] = false;

    for ( int i = 0; i < q; i++ ) {
        if ( queries[i].type == 'Q' ) {
            incc.clear();
            calcIncreasing( queries[i].v, 0, 0 );
            for ( auto p: incc ) {
                if ( p.second <= queries[i].t && p.first == queries[i].u )
                    queries[i].ans = true;
            }
            cout << (queries[i].ans ? "yes\n" : "no\n");
        } else
            cout << queries[i].ans << "\n";
    }

    return 0;
}

Subtask #1
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14136 KB Output is correct
2 Correct 94 ms 15272 KB Output is correct
3 Correct 436 ms 15312 KB Output is correct
4 Correct 80 ms 15304 KB Output is correct
5 Correct 66 ms 15512 KB Output is correct
6 Execution timed out 3561 ms 15852 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 52 ms 14136 KB Output is correct
2 Correct 94 ms 15272 KB Output is correct
3 Correct 436 ms 15312 KB Output is correct
4 Correct 80 ms 15304 KB Output is correct
5 Correct 66 ms 15512 KB Output is correct
6 Execution timed out 3561 ms 15852 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 80 ms 14160 KB Output is correct
2 Execution timed out 3534 ms 23368 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 80 ms 14160 KB Output is correct
2 Execution timed out 3534 ms 23368 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14208 KB Output is correct
2 Correct 173 ms 22452 KB Output is correct
3 Correct 168 ms 22520 KB Output is correct
4 Execution timed out 3523 ms 32196 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 14208 KB Output is correct
2 Correct 173 ms 22452 KB Output is correct
3 Correct 168 ms 22520 KB Output is correct
4 Execution timed out 3523 ms 32196 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14204 KB Output is correct
2 Execution timed out 3512 ms 23000 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 14204 KB Output is correct
2 Execution timed out 3512 ms 23000 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14160 KB Output is correct
2 Correct 195 ms 22496 KB Output is correct
3 Correct 183 ms 22472 KB Output is correct
4 Execution timed out 3566 ms 32280 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 46 ms 14160 KB Output is correct
2 Correct 195 ms 22496 KB Output is correct
3 Correct 183 ms 22472 KB Output is correct
4 Execution timed out 3566 ms 32280 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 14064 KB Output is correct
2 Correct 94 ms 15404 KB Output is correct
3 Correct 439 ms 15236 KB Output is correct
4 Correct 72 ms 15444 KB Output is correct
5 Correct 67 ms 15368 KB Output is correct
6 Execution timed out 3568 ms 15904 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 53 ms 14064 KB Output is correct
2 Correct 94 ms 15404 KB Output is correct
3 Correct 439 ms 15236 KB Output is correct
4 Correct 72 ms 15444 KB Output is correct
5 Correct 67 ms 15368 KB Output is correct
6 Execution timed out 3568 ms 15904 KB Time limit exceeded
7 Halted 0 ms 0 KB -