oj.uz

답안 #581650

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
581650 2022-06-23T00:55:17 Z Lobo Jail (JOI22_jail) C++17
21 / 100
 314 ms 193408 KB 
#include<bits/stdc++.h>
using namespace std;

const long long inf = (long long) 1e19 + 10;
const int inf1 = (int) 1e9 + 10;
// #define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 20e4+10;

int n, m, pp[maxn][20], pai[maxn], gr[40*maxn], h[maxn], s[maxn], t[maxn], up[maxn][20], dw[maxn][20];
vector<int> g[maxn], gts[40*maxn];
int cnt = 0;

void dfslca(int u, int ant) {
    pai[u] = ant;
    pp[u][0] = ant;
    for(int i = 1; i <= 19; i++) {
        pp[u][i] = pp[pp[u][i-1]][i-1];
    }

    //cria up
    up[u][0] = ++cnt;
    for(int i = 1; i <= 19; i++) {
        //liga dos de baixo pra cima
        up[u][i] = ++cnt;
        gts[up[u][i-1]].pb(up[u][i]);
        gts[up[pp[u][i-1]][i-1]].pb(up[u][i]);
    }

    //cria dw
    dw[u][0] = ++cnt;
    for(int i = 1; i <= 19; i++) {
        //liga do de cima para os debaixo
        dw[u][i] = ++cnt;
        gts[dw[u][i]].pb(dw[u][i-1]);
        gts[dw[u][i]].pb(dw[pp[u][i-1]][i-1]);
    }

    for(auto v : g[u]) if(v != ant) {
        h[v] = h[u]+1;
        dfslca(v,u);
    }
}

int lca(int u, int v) {
    if(h[u] < h[v]) swap(u,v);
    for(int i = 19; i >= 0; i--) {
        if(h[pp[u][i]] >= h[v]) {
            u = pp[u][i];
        }
    }
    if(u == v) return u;
    for(int i = 19; i >= 0; i--) {
        if(pp[u][i] != pp[v][i]) {
            u = pp[u][i];
            v = pp[v][i];
        }
    }
    return pp[u][0];
}

void solve() {
    cin >> n;
    cnt = 0;
    for(int i = 0; i <= n; i++) {
        g[i].clear();
    }
    for(int i = 0; i <= n*40; i++) {
        gts[i].clear();
        gr[i] = 0;
    }
    for(int i = 0; i < n-1; i++) {
        int u,v; cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    cin >> m;
    cnt = m;
    h[0] = 0;
    h[1] = 1;
    dfslca(1,0);
    for(int i = 1; i <= m; i++) {
        cin >> s[i] >> t[i];
        if(s[i] == t[i]) return;
        //liga do i para s[i] e t[i]
        gts[i].pb(up[s[i]][0]);
        gts[dw[t[i]][0]].pb(i);
    }

    for(int i = 1; i <= m; i++) {
        int lc = lca(s[i],t[i]);
        // cout << s[i] << " "<< t[i] << " " << lc << endl;
        int v;
        //nao quero ligar do s[i] ate mim, entao faco o dw separado
        gts[i].pb(dw[s[i]][0]);
        v = pai[s[i]];
        //quero ir ate um antes do lc
        for(int j = 19; j >= 0; j--) {
            if(v != 0 && h[pp[v][j]] >= h[lc]) {
                gts[i].pb(dw[v][j]);
                gts[up[v][j]].pb(i);
                v = pp[v][j];
            }
        }
        
        gts[up[t[i]][0]].pb(i);
        v = pai[t[i]];
        //quero ir ate um antes do lc
        for(int j = 19; j >= 0; j--) {
            if(v != 0 && h[pp[v][j]] >= h[lc]) {
                gts[i].pb(dw[v][j]);
                gts[up[v][j]].pb(i);
                v = pp[v][j];
            }
        }

        if(lc != s[i] && lc != t[i]) {
            gts[i].pb(dw[lc][0]);
            gts[up[lc][0]].pb(i);
        }
    }

    for(int i = 1; i <= cnt; i++) {
        for(auto v : gts[i]) {
            gr[v]++;
        }
    }

    queue<int> q;
    for(int i = 1; i <= cnt; i++) {
        // cout << i << " " << gr[i] << endl;
        if(gr[i] == 0) q.push(i);
    }

    while(q.size()) {
        int u = q.front();
        q.pop();
        for(auto v : gts[u]) {
            if(--gr[v] == 0) q.push(v);
        }
    }

    string ans = "Yes";
    for(int i = 1; i <= m; i++) {
        if(gr[i] != 0) ans = "No";
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false); cin.tie(0);

    // freopen("in.in", "r", stdin);
    // freopen("out.out", "w", stdout);
    int tt = 1;
    cin >> tt;
    while(tt--) {
        solve();
    }

}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 192836 KB Output is correct
2 Correct 92 ms 192884 KB Output is correct
3 Correct 88 ms 192876 KB Output is correct
4 Correct 199 ms 193176 KB Output is correct
5 Correct 314 ms 193168 KB Output is correct
6 Correct 102 ms 193300 KB Output is correct
7 Correct 100 ms 193344 KB Output is correct
8 Incorrect 99 ms 193356 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 192860 KB Output is correct
2 Correct 87 ms 192860 KB Output is correct
3 Correct 99 ms 193268 KB Output is correct
4 Correct 100 ms 193356 KB Output is correct
5 Correct 102 ms 193388 KB Output is correct
6 Correct 97 ms 193288 KB Output is correct
7 Correct 108 ms 193408 KB Output is correct
8 Correct 114 ms 193368 KB Output is correct
9 Correct 97 ms 193312 KB Output is correct
10 Correct 99 ms 193292 KB Output is correct
11 Correct 99 ms 193348 KB Output is correct
12 Correct 95 ms 193264 KB Output is correct
13 Correct 97 ms 193356 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 192860 KB Output is correct
2 Correct 87 ms 192860 KB Output is correct
3 Correct 99 ms 193268 KB Output is correct
4 Correct 100 ms 193356 KB Output is correct
5 Correct 102 ms 193388 KB Output is correct
6 Correct 97 ms 193288 KB Output is correct
7 Correct 108 ms 193408 KB Output is correct
8 Correct 114 ms 193368 KB Output is correct
9 Correct 97 ms 193312 KB Output is correct
10 Correct 99 ms 193292 KB Output is correct
11 Correct 99 ms 193348 KB Output is correct
12 Correct 95 ms 193264 KB Output is correct
13 Correct 97 ms 193356 KB Output is correct
14 Correct 87 ms 192872 KB Output is correct
15 Correct 91 ms 192864 KB Output is correct
16 Correct 111 ms 193312 KB Output is correct
17 Correct 101 ms 193356 KB Output is correct
18 Correct 102 ms 193392 KB Output is correct
19 Correct 89 ms 192952 KB Output is correct
20 Correct 99 ms 193296 KB Output is correct
21 Correct 96 ms 193344 KB Output is correct
22 Correct 98 ms 193356 KB Output is correct
23 Correct 90 ms 192916 KB Output is correct
24 Correct 107 ms 193068 KB Output is correct
25 Correct 107 ms 193356 KB Output is correct
26 Correct 90 ms 193228 KB Output is correct
27 Correct 100 ms 193380 KB Output is correct
28 Correct 91 ms 192928 KB Output is correct

Subtask #4
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 192860 KB Output is correct
2 Correct 87 ms 192860 KB Output is correct
3 Correct 99 ms 193268 KB Output is correct
4 Correct 100 ms 193356 KB Output is correct
5 Correct 102 ms 193388 KB Output is correct
6 Correct 97 ms 193288 KB Output is correct
7 Correct 108 ms 193408 KB Output is correct
8 Correct 114 ms 193368 KB Output is correct
9 Correct 97 ms 193312 KB Output is correct
10 Correct 99 ms 193292 KB Output is correct
11 Correct 99 ms 193348 KB Output is correct
12 Correct 95 ms 193264 KB Output is correct
13 Correct 97 ms 193356 KB Output is correct
14 Correct 87 ms 192872 KB Output is correct
15 Correct 91 ms 192864 KB Output is correct
16 Correct 111 ms 193312 KB Output is correct
17 Correct 101 ms 193356 KB Output is correct
18 Correct 102 ms 193392 KB Output is correct
19 Correct 89 ms 192952 KB Output is correct
20 Correct 99 ms 193296 KB Output is correct
21 Correct 96 ms 193344 KB Output is correct
22 Correct 98 ms 193356 KB Output is correct
23 Correct 90 ms 192916 KB Output is correct
24 Correct 107 ms 193068 KB Output is correct
25 Correct 107 ms 193356 KB Output is correct
26 Correct 90 ms 193228 KB Output is correct
27 Correct 100 ms 193380 KB Output is correct
28 Correct 91 ms 192928 KB Output is correct
29 Incorrect 97 ms 193408 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 192860 KB Output is correct
2 Correct 87 ms 192860 KB Output is correct
3 Correct 99 ms 193268 KB Output is correct
4 Correct 100 ms 193356 KB Output is correct
5 Correct 102 ms 193388 KB Output is correct
6 Correct 97 ms 193288 KB Output is correct
7 Correct 108 ms 193408 KB Output is correct
8 Correct 114 ms 193368 KB Output is correct
9 Correct 97 ms 193312 KB Output is correct
10 Correct 99 ms 193292 KB Output is correct
11 Correct 99 ms 193348 KB Output is correct
12 Correct 95 ms 193264 KB Output is correct
13 Correct 97 ms 193356 KB Output is correct
14 Correct 87 ms 192872 KB Output is correct
15 Correct 91 ms 192864 KB Output is correct
16 Correct 111 ms 193312 KB Output is correct
17 Correct 101 ms 193356 KB Output is correct
18 Correct 102 ms 193392 KB Output is correct
19 Correct 89 ms 192952 KB Output is correct
20 Correct 99 ms 193296 KB Output is correct
21 Correct 96 ms 193344 KB Output is correct
22 Correct 98 ms 193356 KB Output is correct
23 Correct 90 ms 192916 KB Output is correct
24 Correct 107 ms 193068 KB Output is correct
25 Correct 107 ms 193356 KB Output is correct
26 Correct 90 ms 193228 KB Output is correct
27 Correct 100 ms 193380 KB Output is correct
28 Correct 91 ms 192928 KB Output is correct
29 Incorrect 97 ms 193408 KB Output isn't correct
30 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 88 ms 192856 KB Output is correct
2 Correct 92 ms 192844 KB Output is correct
3 Correct 105 ms 192916 KB Output is correct
4 Correct 96 ms 192904 KB Output is correct
5 Incorrect 148 ms 193008 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 87 ms 192836 KB Output is correct
2 Correct 92 ms 192884 KB Output is correct
3 Correct 88 ms 192876 KB Output is correct
4 Correct 199 ms 193176 KB Output is correct
5 Correct 314 ms 193168 KB Output is correct
6 Correct 102 ms 193300 KB Output is correct
7 Correct 100 ms 193344 KB Output is correct
8 Incorrect 99 ms 193356 KB Output isn't correct
9 Halted 0 ms 0 KB -