oj.uz

Submission #948934

# Submission time Handle Problem Language Result Execution time Memory
948934 2024-03-18T16:43:19 Z LucaIlie Inside information (BOI21_servers) C++17
0 / 100
 18 ms 30672 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 + 1];
    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 = sz - sizee[u];
    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] );
    }

    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] ) {
                if ( edges[e].t <= queries[q].t && timee.qry( queries[q].u ) <= queries[q].t )
                    queries[q].ans = true;
            }
            for ( int q: queriesC[u] ) { 
                if ( edges[e].t <= queries[q].t )
                    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] ) {
        if ( timee.qry( queries[q].u ) <= queries[q].t )
            queries[q].ans = true;
    }
    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() {
    ifstream cin( ".in" );
    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();
    decomp( 1 );

    for ( int i = 0; i < q; i++ ) {
        if ( queries[i].type == 'Q' )
            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 Runtime error 17 ms 30672 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Runtime error 17 ms 30672 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 30608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Runtime error 18 ms 30608 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 12632 KB Output isn't correct
2 Halted 0 ms 0 KB -