Submission #948931

#	Time	Username	Problem	Language	Result	Execution time	Memory
948931		LucaIlie	Inside information (BOI21_servers)	C++17	50 / 100	421 ms	38472 KiB

servers

#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] )
                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() {
    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 = 1; i <= n; i++ )
        isCentroid[i] = false;

    /*for ( int u = 1; u <= n; u++ ) {
        for ( int i: queriesQ[u] ) {
            incc.clear();
            calcIncreasing( queries[i].v, 0, 0 );
            bool ans = false;
            for ( auto p: incc ) {
                if ( p.second <= queries[i].t && p.first == queries[i].u )
                    ans = true;
            }
            if ( ans != queries[i].ans )
                printf( "%d %d %d\n", queries[i].u, queries[i].v, ans );
            queries[i].ans = ans;
        }
    }*/

    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: 2.5 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 2.5 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 5 / 5
• Subtask 6: 0 / 5
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 12.5 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 17.5 / 17.5
• Subtask 12: 0 / 17.5