oj.uz

답안 #723651

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723651 2023-04-14T07:03:25 Z anusha777 Railway (BOI17_railway) C++14
23 / 100
 1000 ms 19220 KB 
#include <bits/stdc++.h>
#define fast 			ios::sync_with_stdio(0); cin.tie(NULL);cout.tie(NULL)
#define sz(x)			(int)((x).size())
#define pb				push_back
#define vi				vector<int>
#define vb				vector<bool>
#define vvb				vector<vb>
#define pi				pair<int,int>
#define vpi				vector<pi>
#define vvi				vector<vi>
#define vc				vector<char>
#define all(x)			x.begin(), x.end()
#define rall(x)			x.rbegin(), x.rend()
#define pbb()			pop_back()
#define f				first
#define s				second
#define ll				long long
#define int				long long
#define ull				unsigned long long
#define line               cout<<"_____________________________"<<endl;
#define forr(i, a, b)      for(int i=a; i<b; i++)
const int N=1e5+1, mod=1e9+7, inf=1e18+1;
using namespace std;
vpi out[N];
int f[N]={0};
int n, m,k;
bool take[N];
vpi a;
void init()
{
    forr(i, 0, N) take[i]=0;
}

void dfs(int u, int p)
{
    if(take[u]) for(int i=sz(a)-1; i>=0 and a[i].s==0; i--)
    {
        f[a[i].first]++;
        a[i].second=1;
    }
    for(pi v: out[u]) if(p!=v.f)
        {
            a.pb({v.s, 0});
            dfs(v.f, u);
        }
    a.pbb();
}
void task()
{
    cin>>n>>m>>k;
    forr(i, 1, n)
    {
        int u, v;
        cin>>u>>v;
        out[u].pb({v,i});
        out[v].pb({u,i});
    }
    while (m--)
    {
        int s;
        cin>>s;
        init();
        int start=-1;
        while(s--)
        {
            cin>>start;
            take[start]=1;
        }
        dfs(start, 0);
        a.clear();
    }
    vi b;
    for(int i=1; i<n; i++) if(f[i]>=k) b.pb(i);
    cout<<sz(b)<<endl;
    for(int t: b) cout<<t<<' ';
    cout<<endl;
}
signed main()
{
    fast;
    int t;
    t=1;
    //cin>>t;
    while(t--)task();
}

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 55 ms 3412 KB Output is correct
3 Correct 60 ms 3412 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 87 ms 4172 KB Output is correct
7 Correct 26 ms 3580 KB Output is correct
8 Correct 133 ms 3420 KB Output is correct
9 Correct 137 ms 3444 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 55 ms 3412 KB Output is correct
3 Correct 60 ms 3412 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 87 ms 4172 KB Output is correct
7 Correct 26 ms 3580 KB Output is correct
8 Correct 133 ms 3420 KB Output is correct
9 Correct 137 ms 3444 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 311 ms 3844 KB Output is correct
16 Correct 324 ms 3812 KB Output is correct
17 Correct 342 ms 3848 KB Output is correct
18 Correct 356 ms 4044 KB Output is correct
19 Correct 191 ms 3580 KB Output is correct
20 Correct 149 ms 4000 KB Output is correct
21 Correct 140 ms 3816 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 45 ms 3412 KB Output is correct
24 Correct 43 ms 3412 KB Output is correct
25 Correct 2 ms 2772 KB Output is correct
26 Correct 2 ms 2668 KB Output is correct
27 Correct 78 ms 4132 KB Output is correct
28 Correct 22 ms 3540 KB Output is correct
29 Correct 133 ms 3436 KB Output is correct
30 Correct 128 ms 3328 KB Output is correct
31 Correct 2 ms 2772 KB Output is correct
32 Correct 2 ms 2772 KB Output is correct
33 Correct 2 ms 2644 KB Output is correct
34 Correct 2 ms 2772 KB Output is correct
35 Correct 2 ms 2680 KB Output is correct

Subtask #3
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1083 ms 19220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 14144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1064 ms 14144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 55 ms 3412 KB Output is correct
3 Correct 60 ms 3412 KB Output is correct
4 Correct 2 ms 2772 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 87 ms 4172 KB Output is correct
7 Correct 26 ms 3580 KB Output is correct
8 Correct 133 ms 3420 KB Output is correct
9 Correct 137 ms 3444 KB Output is correct
10 Correct 2 ms 2644 KB Output is correct
11 Correct 3 ms 2772 KB Output is correct
12 Correct 2 ms 2772 KB Output is correct
13 Correct 2 ms 2772 KB Output is correct
14 Correct 2 ms 2644 KB Output is correct
15 Correct 311 ms 3844 KB Output is correct
16 Correct 324 ms 3812 KB Output is correct
17 Correct 342 ms 3848 KB Output is correct
18 Correct 356 ms 4044 KB Output is correct
19 Correct 191 ms 3580 KB Output is correct
20 Correct 149 ms 4000 KB Output is correct
21 Correct 140 ms 3816 KB Output is correct
22 Correct 2 ms 2644 KB Output is correct
23 Correct 45 ms 3412 KB Output is correct
24 Correct 43 ms 3412 KB Output is correct
25 Correct 2 ms 2772 KB Output is correct
26 Correct 2 ms 2668 KB Output is correct
27 Correct 78 ms 4132 KB Output is correct
28 Correct 22 ms 3540 KB Output is correct
29 Correct 133 ms 3436 KB Output is correct
30 Correct 128 ms 3328 KB Output is correct
31 Correct 2 ms 2772 KB Output is correct
32 Correct 2 ms 2772 KB Output is correct
33 Correct 2 ms 2644 KB Output is correct
34 Correct 2 ms 2772 KB Output is correct
35 Correct 2 ms 2680 KB Output is correct
36 Execution timed out 1083 ms 19220 KB Time limit exceeded
37 Halted 0 ms 0 KB -