Submission #423871

#	Time	Username	Problem	Language	Result	Execution time	Memory
423871		zoooma13	Inside information (BOI21_servers)	C++14	0 / 100	60 ms	11568 KiB

servers

#include <bits/stdc++.h>
using namespace std;

#define MAX_N 120005
#define LOG_N 17

struct DSU{
    vector <int> e;
    DSU(int n) : e(n ,-1) {}
    int find(int x) { return e[x]<0? x : e[x]=find(e[x]); }
    int size(int x) { return -e[find(x)]; }
    bool join(int x ,int y){
        x = find(x) ,y = find(y);
        if(x == y) return false;
        if(e[x] > e[y]) swap(x ,y);
        e[x] += e[y]; e[y] = x;
        return true;
    }
};

struct query{
    int type ,time ,fr ,to;
};

int tin[MAX_N] ,tout[MAX_N] ,tt;
int val[MAX_N] ,dis[MAX_N];
int par[LOG_N][MAX_N] ,inv[LOG_N][MAX_N];
vector <vector <pair<int ,int>>> adj;
void pre(int u){
    tin[u] = ++tt;
    for(int j = 1; (1<<j) <= dis[u]; j++){
        par[j][u] = par[j-1][par[j-1][u]];
        inv[j][u] = inv[j-1][u] + inv[j-1][par[j-1][u]];
    }
//    cout << "at " << u << " val = " << val[u] << " and inv = " << inv[0][u] << endl;
    for(auto&e : adj[u]) if(e.first != par[0][u]){
        val[e.first] = e.second;
        par[0][e.first] = u;
        inv[0][e.first] = e.second > val[u];
        dis[e.first] = dis[u]+1;
        pre(e.first);
    }
    tout[u] = tt;
}
bool isAnc(int u ,int v){ //is u ancestor of v?
    return tin[u] <= tin[v] && tout[v] <= tout[u];
}

int main()
{   int n ,k;
    scanf("%d%d",&n,&k);
    adj.resize(n+1);
    vector <query> qs;
    for(int t = 1; t < n+k; t++){
        char q; int x ,y;
        scanf(" %c%d",&q,&x);
        if(q == 'S'){
            scanf("%d",&y);
            adj[x].push_back({y ,t});
            adj[y].push_back({x ,t});
            qs.push_back({0 ,t ,x ,y});
        }
        else if(q == 'Q'){
            scanf("%d",&y);
            qs.push_back({1 ,t ,x ,y});
        }
        else
            qs.push_back({2 ,t ,x ,-1});
    }

    memset(par ,-1 ,sizeof par);
    par[0][1] = 1;
    pre(1);

    DSU d(n+1);
    for(query&q : qs){
        if(q.type == 0){
            d.join(q.fr ,q.to);
        }
        else if(q.type == 1){
            if(d.find(q.fr) != d.find(q.to))
                printf("no\n");
            else{
                int a = q.to ,b = q.fr;
                for(int j = LOG_N-1; ~j; j--)
                    if(par[j][a] != -1 && inv[j][a] == 0)
                        a = par[j][a];
                for(int j = LOG_N-1; ~j; j--)
                    if(par[j][b] != -1 && inv[j][b] == (1<<j))
                        b = par[j][b];
//                cout << q.to << " can reach " << a << endl;
//                cout << q.fr << " can reach " << b << endl;
                if(dis[a] < dis[b])
                    swap(a ,b);
                a = par[0][a];

                int u = q.to ,v = q.fr;
                for(int j = LOG_N-1; ~j; j--) if((dis[u]-dis[a]-1)>>j&1)
                        u = par[j][u];
                for(int j = LOG_N-1; ~j; j--) if((dis[v]-dis[a]-1)>>j&1)
                        v = par[j][v];

//                cout << "a = " << a << endl;
//                cout << tin[a] << ' ' << tout[a] << endl;
                if(isAnc(a ,q.fr) && isAnc(a ,q.to) && val[u] <= val[v])
                    printf("yes\n");
                else
                    printf("no\n");
            }
        }
    }
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |     scanf("%d%d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~
servers.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |         scanf(" %c%d",&q,&x);
      |         ~~~~~^~~~~~~~~~~~~~~
servers.cpp:58:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |             scanf("%d",&y);
      |             ~~~~~^~~~~~~~~
servers.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf("%d",&y);
      |             ~~~~~^~~~~~~~~

• Subtask 1: 0 / 2.5
• Subtask 2: 0 / 2.5
• Subtask 3: 0 / 2.5
• Subtask 4: 0 / 2.5
• Subtask 5: 0 / 5
• Subtask 6: 0 / 5
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 12.5
• Subtask 10: 0 / 12.5
• Subtask 11: 0 / 17.5
• Subtask 12: 0 / 17.5