oj.uz

답안 #402236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
402236 2021-05-11T12:55:13 Z doowey Inside information (BOI21_servers) C++14
0 / 100
 364 ms 30852 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = 120101;
vector<pii> T[N];
vector<pii> qq[N];
vector<int> cnt[N];

bool del[N];
int sub[N];

int num[N];
int iq[N];
int iter;
bool inc[N];
bool dem[N];

int outp[N];
int in[N];

ll shd[N];

void dfs(int u, int pa){
    sub[u]=1;
    num[u]=-1;
    iq[u]=iter;
    for(auto x : T[u]){
        if(x.fi==pa || del[x.fi]) continue;
        dfs(x.fi, u);
        sub[u] += sub[x.fi];
    }
}

void dfs2(int u, int pa, int ss, int l1, int l2){
    num[u] = ss;
    in[u] = l2;
    if(l1 == -1 || l2 == -1) inc[u]=dem[u]=true;
    else{
        if(l1 > l2){
            inc[u]=inc[pa];
            dem[u]=false;
        }
        else{
            inc[u]=false;
            dem[u]=dem[pa];
        }
    }
    for(auto x : qq[u]){
        if(iq[x.fi] == iq[u]){
            if(num[x.fi] == 0){
                if(inc[u] && shd[ss] <= x.se){
                    outp[x.se] = -1;
                }
                else{
                    outp[x.se] = -2;
                }
            }
            else if(num[x.fi] == -1){
                outp[x.se] = -2;
            }
            else if(num[u] != num[x.fi]){
                if(inc[u] && dem[x.fi] && in[x.fi] <= x.se){
                    outp[x.se] = -1;
                }
                else{
                    outp[x.se] = -2;
                }
            }
        }
    }
    for(auto x : T[u]){
        if(x.fi==pa || del[x.fi]) continue;
        dfs2(x.fi, u, ss, l2, x.se);
    }
}

bool comp(pii a, pii b){
    return a.se > b.se;
}

void decomp(int node){
    iter ++ ;
    dfs(node, -1);
    int pp = -1;
    bool go = true;
    int sz = sub[node];
    while(go){
        go = false;
        for(auto x : T[node]){
            if(x.fi == pp || del[x.fi]) continue;
            if(sub[x.fi] > sz / 2){
                go = true;
                pp = node;
                node = x.fi;
                break;
            }
        }
    }
    sort(T[node].begin(), T[node].end(), comp);
    num[node] = 0;
    int cc = 1;
    inc[node]=dem[node]=true;
    for(auto x : T[node]){
        if(del[x.fi]) continue;
        shd[cc] = x.se;
        dfs2(x.fi, node, cc, -1, x.se);
        cc ++ ;
    }
    for(auto x : qq[node]){
        if(iq[node] == iq[x.fi]){

            if(dem[x.fi] && in[x.fi] <= x.se){
                outp[x.se] = -1;
            }
            else{
                outp[x.se] = -2;
            }
        }
    }
    del[node]=true;

    for(auto x : T[node]){
        if(!del[x.fi])
            decomp(x.fi);
    }



}

int main(){
    fastIO;
    int n, q;
    cin >> n >> q;
    char typ;
    int x, y;
    for(int iq = 1; iq <= n + q - 1; iq ++ ){
        cin >> typ;
        if(typ == 'S'){
            cin >> x >> y;
            T[x].push_back(mp(y, iq));
            T[y].push_back(mp(x, iq));
        }
        else if(typ == 'Q'){
            cin >> x >> y; // is there an increasing path from y to x
            if(x == y){
                outp[iq] = -1;
            }
            else{
                qq[y].push_back(mp(x, iq));
            }
        }
        else{
            cin >> x;
            cnt[x].push_back(iq);
        }
    }
    decomp(1);
    for(int oo = 1; oo <= n + q - 1; oo ++ ){
        if(outp[oo] == 0) continue;
        if(outp[oo] == -1){
            cout << "yes\n";
        }
        else if(outp[oo] == -2){
            cout << "no\n";
        }
        else{
            cout << outp[oo] << "\n";
        }
    }
    return 0;
}

Subtask #1
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 11132 KB Output is correct
2 Incorrect 53 ms 12888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 11132 KB Output is correct
2 Incorrect 53 ms 12888 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 11144 KB Output is correct
2 Incorrect 197 ms 23196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 2.5

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 11144 KB Output is correct
2 Incorrect 197 ms 23196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 11128 KB Output is correct
2 Incorrect 364 ms 30808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 11128 KB Output is correct
2 Incorrect 364 ms 30808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 11120 KB Output is correct
2 Incorrect 209 ms 22748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 11120 KB Output is correct
2 Incorrect 209 ms 22748 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 11200 KB Output is correct
2 Incorrect 362 ms 30852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 12.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 11200 KB Output is correct
2 Incorrect 362 ms 30852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 11228 KB Output is correct
2 Incorrect 47 ms 12900 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #12
0 / 17.5

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 11228 KB Output is correct
2 Incorrect 47 ms 12900 KB Output isn't correct
3 Halted 0 ms 0 KB -