oj.uz

Submission #948931

# Submission time Handle Problem Language Result Execution time Memory
948931 2024-03-18T16:41:59 Z LucaIlie Inside information (BOI21_servers) C++17
50 / 100
 421 ms 38472 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] )
                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

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14160 KB Output is correct
2 Correct 59 ms 15700 KB Output is correct
3 Correct 57 ms 15676 KB Output is correct
4 Correct 68 ms 15700 KB Output is correct
5 Correct 62 ms 15960 KB Output is correct
6 Correct 90 ms 16108 KB Output is correct

Subtask #2
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 41 ms 14160 KB Output is correct
2 Correct 59 ms 15700 KB Output is correct
3 Correct 57 ms 15676 KB Output is correct
4 Correct 68 ms 15700 KB Output is correct
5 Correct 62 ms 15960 KB Output is correct
6 Correct 90 ms 16108 KB Output is correct
7 Incorrect 42 ms 15036 KB Extra information in the output file
8 Halted 0 ms 0 KB -

Subtask #3
2.5 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14420 KB Output is correct
2 Correct 234 ms 33288 KB Output is correct
3 Correct 207 ms 34596 KB Output is correct

Subtask #4
0 / 2.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14420 KB Output is correct
2 Correct 234 ms 33288 KB Output is correct
3 Correct 207 ms 34596 KB Output is correct
4 Incorrect 41 ms 15188 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14248 KB Output is correct
2 Correct 407 ms 32200 KB Output is correct
3 Correct 392 ms 32416 KB Output is correct
4 Correct 298 ms 38472 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14248 KB Output is correct
2 Correct 407 ms 32200 KB Output is correct
3 Correct 392 ms 32416 KB Output is correct
4 Correct 298 ms 38472 KB Output is correct
5 Incorrect 45 ms 15092 KB Extra information in the output file
6 Halted 0 ms 0 KB -

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14164 KB Output is correct
2 Correct 284 ms 25784 KB Output is correct
3 Correct 317 ms 23876 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14164 KB Output is correct
2 Correct 284 ms 25784 KB Output is correct
3 Correct 317 ms 23876 KB Output is correct
4 Incorrect 47 ms 15124 KB Extra information in the output file
5 Halted 0 ms 0 KB -

Subtask #9
12.5 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14220 KB Output is correct
2 Correct 390 ms 32632 KB Output is correct
3 Correct 406 ms 32240 KB Output is correct
4 Correct 300 ms 37076 KB Output is correct
5 Correct 42 ms 15200 KB Output is correct
6 Correct 279 ms 26932 KB Output is correct
7 Correct 269 ms 23904 KB Output is correct
8 Correct 305 ms 24840 KB Output is correct
9 Correct 330 ms 24568 KB Output is correct
10 Correct 407 ms 28732 KB Output is correct
11 Correct 421 ms 28304 KB Output is correct

Subtask #10
0 / 12.5

# Verdict Execution time Memory Grader output
1 Correct 43 ms 14220 KB Output is correct
2 Correct 390 ms 32632 KB Output is correct
3 Correct 406 ms 32240 KB Output is correct
4 Correct 300 ms 37076 KB Output is correct
5 Correct 42 ms 15200 KB Output is correct
6 Correct 279 ms 26932 KB Output is correct
7 Correct 269 ms 23904 KB Output is correct
8 Correct 305 ms 24840 KB Output is correct
9 Correct 330 ms 24568 KB Output is correct
10 Correct 407 ms 28732 KB Output is correct
11 Correct 421 ms 28304 KB Output is correct
12 Incorrect 45 ms 15220 KB Extra information in the output file
13 Halted 0 ms 0 KB -

Subtask #11
17.5 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14164 KB Output is correct
2 Correct 60 ms 15700 KB Output is correct
3 Correct 57 ms 15724 KB Output is correct
4 Correct 64 ms 15696 KB Output is correct
5 Correct 61 ms 15920 KB Output is correct
6 Correct 63 ms 16100 KB Output is correct
7 Correct 41 ms 15188 KB Output is correct
8 Correct 209 ms 35004 KB Output is correct
9 Correct 188 ms 33724 KB Output is correct
10 Correct 41 ms 15096 KB Output is correct
11 Correct 387 ms 33580 KB Output is correct
12 Correct 318 ms 33616 KB Output is correct
13 Correct 291 ms 38228 KB Output is correct
14 Correct 46 ms 15104 KB Output is correct
15 Correct 261 ms 27232 KB Output is correct
16 Correct 281 ms 23892 KB Output is correct
17 Correct 268 ms 24832 KB Output is correct
18 Correct 288 ms 24576 KB Output is correct
19 Correct 335 ms 28728 KB Output is correct
20 Correct 334 ms 28472 KB Output is correct
21 Correct 203 ms 30508 KB Output is correct
22 Correct 219 ms 29392 KB Output is correct
23 Correct 232 ms 24716 KB Output is correct
24 Correct 255 ms 24820 KB Output is correct
25 Correct 395 ms 33668 KB Output is correct
26 Correct 346 ms 23672 KB Output is correct
27 Correct 277 ms 23508 KB Output is correct

Subtask #12
0 / 17.5

# Verdict Execution time Memory Grader output
1 Correct 42 ms 14164 KB Output is correct
2 Correct 60 ms 15700 KB Output is correct
3 Correct 57 ms 15724 KB Output is correct
4 Correct 64 ms 15696 KB Output is correct
5 Correct 61 ms 15920 KB Output is correct
6 Correct 63 ms 16100 KB Output is correct
7 Correct 41 ms 15188 KB Output is correct
8 Correct 209 ms 35004 KB Output is correct
9 Correct 188 ms 33724 KB Output is correct
10 Correct 41 ms 15096 KB Output is correct
11 Correct 387 ms 33580 KB Output is correct
12 Correct 318 ms 33616 KB Output is correct
13 Correct 291 ms 38228 KB Output is correct
14 Correct 46 ms 15104 KB Output is correct
15 Correct 261 ms 27232 KB Output is correct
16 Correct 281 ms 23892 KB Output is correct
17 Correct 268 ms 24832 KB Output is correct
18 Correct 288 ms 24576 KB Output is correct
19 Correct 335 ms 28728 KB Output is correct
20 Correct 334 ms 28472 KB Output is correct
21 Correct 203 ms 30508 KB Output is correct
22 Correct 219 ms 29392 KB Output is correct
23 Correct 232 ms 24716 KB Output is correct
24 Correct 255 ms 24820 KB Output is correct
25 Correct 395 ms 33668 KB Output is correct
26 Correct 346 ms 23672 KB Output is correct
27 Correct 277 ms 23508 KB Output is correct
28 Incorrect 42 ms 15164 KB Extra information in the output file
29 Halted 0 ms 0 KB -