oj.uz

답안 #423871

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423871 2021-06-11T13:35:03 Z zoooma13 Inside information (BOI21_servers) C++14
0 / 100
 60 ms 11568 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 11568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 56 ms 11568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 11472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 11472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 11540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 45 ms 11540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 11480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 11480 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 11536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 44 ms 11536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 11496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 11496 KB Output isn't correct
2 Halted 0 ms 0 KB -