oj.uz

Submission #441670

# Submission time Handle Problem Language Result Execution time Memory
441670 2021-07-05T18:22:41 Z Mahfel Railway (BOI17_railway) C++17
23 / 100
 1000 ms 35908 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MXN = 1e5 + 20 , LOG = 19;
vector<int> adj[MXN];
vector<int> euler;
map<pair<int,int>,int> idx;
int st_time[MXN] , sz[MXN] , p[LOG][MXN] , h[MXN];
int d[MXN] , ans[MXN] , sm[MXN];
int n,m,k;
 
struct seg_tree {
    int size;
    vector<int> v;
    seg_tree() {
        size = 1;
        while(size < n) size <<= 1;
        v.assign(2*size , 0);
    }
 
    void add(int x , int lx , int rx , int i , int k) {
        if(rx-lx == 1) {
            v[x] += k; return;
        }
        int m = (lx+rx)/2;
        if(i < m) {
            add(2*x+1 , lx , m , i , k);
        } else {
            add(2*x+2 , m , rx , i , k);
        }
        v[x] = v[2*x+1] + v[2*x+2];
    }
    void add(int i , int k) {
        add(0 , 0 , size , i , k);
    }
 
    int sum(int x , int lx , int rx , int l , int r) {
        if(lx >= l && rx <= r) {
            return v[x];
        }
        if(lx >= r || rx <= l) {
            return 0;
        }
        int m = (lx+rx)/2;
        return sum(2*x+1 , lx , m , l , r) + sum(2*x+2 , m , rx , l , r);
    }
    int sum(int l , int r) {
        return sum(0 , 0 , size , l , r);
    }
};
 
struct fenwick {
    vector<int> v;
    fenwick() {
        v.assign(n , 0);
    }
 
    void add(int i , int k) {
        for(; i < n ; i = (i|(i+1))) {
            v[i] += k;
        }
    }
 
    int sum(int x) {
        if(x < 0) return 0;
        int ans = 0;
        for(; x >= 0 ; x = (x&(x+1))-1) {
            ans += v[x];
        }
        return ans;
    }
    int sum(int l , int r) {
        return sum(r)-sum(l-1);
    }
};
 
void DFS(int v , int dad) {
    euler.push_back(v); st_time[v] = euler.size()-1;
    sz[v] = 1;
    p[0][v] = (dad == -1 ? v : dad);
    h[v] = (dad == -1 ? 0 : h[dad]+1);
    for(auto u : adj[v]) {
        if(u == dad) continue;
        DFS(u , v);
        sz[v] += sz[u];
    }
}
 
void final_DFS(int v , int dad) {
    int res = d[v];
    for(auto u : adj[v]) {
        if(u == dad) continue;
        final_DFS(u , v);
        res += sm[u];
    }
    sm[v] = res;
    if(dad != -1) ans[idx[{v , dad}]] = res;
}
 
void build_LCA() {
    for(int i = 1 ; i < LOG ; i++) {
        for(int j = 1 ; j <= n ; j++) {
            p[i][j] = p[i-1][p[i-1][j]];
        }
    }
}
int kth_anc(int k , int v) {
    while(k > 0) {
        int x = __builtin_ctz(k);
        v = p[x][v];
        k -= (1 << x);
    }
    return v;
}
int LCA(int v , int u) {
    if(h[v] > h[u]) swap(v,u);
    u = kth_anc(h[u]-h[v] , u);
    if(u == v) return v;
    for(int i = LOG-1 ; i >= 0 ; i--) {
        if(p[i][v] != p[i][u]) {
            v = p[i][v]; u = p[i][u];
        }
    }
    return p[0][v];
}
 
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
 
    cin >> n >> m >> k;
    for(int i = 1 ; i < n ; i++) {
        int v,u; cin >> v >> u;
        adj[v].push_back(u); adj[u].push_back(v);
        idx[{v , u}] = i; idx[{u , v}] = i;
    }
    DFS(1 , -1);
    build_LCA();
 
    for(int q = 0 ; q < m ; q++) {
 
        fenwick fen;
        int s; cin >> s;
        int v,u; cin >> v >> u;
        int lca = LCA(v , u);
        d[v]++; d[u]++; d[lca] -= 2;
        fen.add(st_time[v] , 1); fen.add(st_time[u] , 1);
        v = lca;
        for(int i = 2 ; i < s ; i++) {
            int u; cin >> u;
            lca = LCA(v , u);
            if(lca != v) {
                d[u]++; d[v]++; d[lca] -= 2;
                fen.add(st_time[u] , 1);
            } else {
                if(fen.sum(st_time[u] , st_time[u]+sz[u]-1) > 0) continue;
                int _u = u;
                for(int i = LOG-1 ; i >= 0 ; i--) {
                    int par = p[i][_u];
                    if(par != 1 && fen.sum(st_time[par] , st_time[par]+sz[par]-1) <= 0) {
                        _u = par;
                    }
                }
                _u = p[0][_u];
                d[u]++; d[_u]--;
                fen.add(st_time[u] , 1);
            }
            v = lca;
        }
    }
 
    final_DFS(1 , -1);
    vector<int> res;
    for(int i = 1 ; i < n ; i++) {
        if(ans[i] >= k) res.push_back(i);
    }
    cout << res.size() << "\n";
    for(auto u : res) {
        cout << u << " ";
    }
    cout << "\n";
 
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 16 ms 5460 KB Output is correct
3 Correct 19 ms 5420 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 16 ms 6092 KB Output is correct
7 Correct 16 ms 5644 KB Output is correct
8 Correct 17 ms 5452 KB Output is correct
9 Correct 18 ms 5516 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 2 ms 2768 KB Output is correct
13 Correct 2 ms 2768 KB Output is correct
14 Correct 2 ms 2764 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 16 ms 5460 KB Output is correct
3 Correct 19 ms 5420 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 16 ms 6092 KB Output is correct
7 Correct 16 ms 5644 KB Output is correct
8 Correct 17 ms 5452 KB Output is correct
9 Correct 18 ms 5516 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 2 ms 2768 KB Output is correct
13 Correct 2 ms 2768 KB Output is correct
14 Correct 2 ms 2764 KB Output is correct
15 Correct 51 ms 5892 KB Output is correct
16 Correct 50 ms 5836 KB Output is correct
17 Correct 49 ms 5848 KB Output is correct
18 Correct 23 ms 6024 KB Output is correct
19 Correct 19 ms 5624 KB Output is correct
20 Correct 37 ms 5956 KB Output is correct
21 Correct 39 ms 5956 KB Output is correct
22 Correct 2 ms 2764 KB Output is correct
23 Correct 16 ms 5452 KB Output is correct
24 Correct 16 ms 5428 KB Output is correct
25 Correct 2 ms 2764 KB Output is correct
26 Correct 2 ms 2764 KB Output is correct
27 Correct 16 ms 6092 KB Output is correct
28 Correct 16 ms 5580 KB Output is correct
29 Correct 17 ms 5440 KB Output is correct
30 Correct 18 ms 5444 KB Output is correct
31 Correct 2 ms 2764 KB Output is correct
32 Correct 2 ms 2764 KB Output is correct
33 Correct 2 ms 2764 KB Output is correct
34 Correct 2 ms 2672 KB Output is correct
35 Correct 2 ms 2768 KB Output is correct

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1094 ms 35908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 32692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 32692 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2764 KB Output is correct
2 Correct 16 ms 5460 KB Output is correct
3 Correct 19 ms 5420 KB Output is correct
4 Correct 2 ms 2764 KB Output is correct
5 Correct 2 ms 2764 KB Output is correct
6 Correct 16 ms 6092 KB Output is correct
7 Correct 16 ms 5644 KB Output is correct
8 Correct 17 ms 5452 KB Output is correct
9 Correct 18 ms 5516 KB Output is correct
10 Correct 2 ms 2764 KB Output is correct
11 Correct 2 ms 2764 KB Output is correct
12 Correct 2 ms 2768 KB Output is correct
13 Correct 2 ms 2768 KB Output is correct
14 Correct 2 ms 2764 KB Output is correct
15 Correct 51 ms 5892 KB Output is correct
16 Correct 50 ms 5836 KB Output is correct
17 Correct 49 ms 5848 KB Output is correct
18 Correct 23 ms 6024 KB Output is correct
19 Correct 19 ms 5624 KB Output is correct
20 Correct 37 ms 5956 KB Output is correct
21 Correct 39 ms 5956 KB Output is correct
22 Correct 2 ms 2764 KB Output is correct
23 Correct 16 ms 5452 KB Output is correct
24 Correct 16 ms 5428 KB Output is correct
25 Correct 2 ms 2764 KB Output is correct
26 Correct 2 ms 2764 KB Output is correct
27 Correct 16 ms 6092 KB Output is correct
28 Correct 16 ms 5580 KB Output is correct
29 Correct 17 ms 5440 KB Output is correct
30 Correct 18 ms 5444 KB Output is correct
31 Correct 2 ms 2764 KB Output is correct
32 Correct 2 ms 2764 KB Output is correct
33 Correct 2 ms 2764 KB Output is correct
34 Correct 2 ms 2672 KB Output is correct
35 Correct 2 ms 2768 KB Output is correct
36 Execution timed out 1094 ms 35908 KB Time limit exceeded
37 Halted 0 ms 0 KB -