oj.uz

Submission #932088

# Submission time Handle Problem Language Result Execution time Memory
932088 2024-02-23T00:48:05 Z irmuun Railway (BOI17_railway) C++17
8 / 100
 1000 ms 22224 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
#define ll int
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,m,k;
    cin>>n>>m>>k;
    vector<int>adj[n+5];
    vector<pair<int,int>>edge;
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        edge.pb({u,v});
        adj[u].pb(v);
        adj[v].pb(u);
    }
    int s[m+5];
    vector<int>need[m+5];
    for(int i=1;i<=m;i++){
        cin>>s[i];
        need[i].resize(s[i]);
        for(int j=0;j<s[i];j++){
            cin>>need[i][j];
        }
    }
    vector<int>par(n+5);
    vector<int>f(n+5),e(n+5);
    int cur=0;
    function <void(int,int)> dfs=[&](int x,int p){
        f[x]=cur++;
        par[x]=p;
        for(auto y:adj[x]){
            if(y!=p){
                dfs(y,x);
            }
        }
        e[x]=cur++;
    };
    dfs(1,0);
    cur=0;
    vector<int>ans,cnt(n+5,0);
    for(auto [x,p]:edge){
        cur++;
        if(par[p]==x) swap(x,p);
        int c=0;
        for(int j=1;j<=m;j++){
            c=0;
            for(auto r:need[j]){
                if(f[x]<=f[r]&&e[r]<=e[x]){
                    c++;
                }
            }
            if(0<c&&c<s[j]){
                cnt[cur]++;
            }
        }
    }
    for(int i=1;i<n;i++){
        if(cnt[i]>=k){
            ans.pb(i);
        }
    }
    cout<<ans.size()<<"\n";
    for(auto i:ans){
        cout<<i<<' ';
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 37 ms 1296 KB Output is correct
3 Correct 38 ms 1372 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 31 ms 1884 KB Output is correct
7 Correct 41 ms 1368 KB Output is correct
8 Correct 43 ms 1368 KB Output is correct
9 Correct 39 ms 1432 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 37 ms 1296 KB Output is correct
3 Correct 38 ms 1372 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 31 ms 1884 KB Output is correct
7 Correct 41 ms 1368 KB Output is correct
8 Correct 43 ms 1368 KB Output is correct
9 Correct 39 ms 1432 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Execution timed out 1089 ms 2028 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1054 ms 22224 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 1091 ms 17588 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 1091 ms 17588 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 37 ms 1296 KB Output is correct
3 Correct 38 ms 1372 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 31 ms 1884 KB Output is correct
7 Correct 41 ms 1368 KB Output is correct
8 Correct 43 ms 1368 KB Output is correct
9 Correct 39 ms 1432 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Execution timed out 1089 ms 2028 KB Time limit exceeded
16 Halted 0 ms 0 KB -