oj.uz

Submission #950070

# Submission time Handle Problem Language Result Execution time Memory
950070 2024-03-20T04:54:45 Z Abito Tourism (JOI23_tourism) C++17
5 / 100
 22 ms 62348 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=305;
int n,par[N][N],b[N],m,q,euler[N][2*N],c,dis[N][N],f[N][N],lg[2*N];
vector<int> adj[N];
bool vis[N];
pair<int,int> st[N][20][2*N];
void dfs(int x,int p,int r){
    par[r][x]=p;
    euler[r][++c]=x;
    f[r][x]=c;
    dis[r][x]=dis[r][p]+1;
    for (auto u:adj[x]){
        if (u==p) continue;
        dfs(u,x,r);
        euler[r][++c]=x;
    }
    return;
}
void build(){
    for (int r=1;r<=n;r++){
    for (int i=1;i<=c;i++) st[r][0][i]={dis[r][euler[r][i]],euler[r][i]};
    for (int i=1;i<20;i++){
        for (int j=1;j+(1<<i)<=c+1;j++){
            st[r][i][j]=min(st[r][i-1][j],st[r][i-1][j+(1<<(i-1))]);
        }
    }}return;
}
int query(int l,int r,int x){
    if (l>r) swap(l,r);
    int i=lg[r-l+1];
    return min(st[x][i][l],st[x][i][r-(1<<i)+1]).S;
}
int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    for (int i=2;i<2*N;i++) lg[i]=lg[i/2]+1;
    cin>>n>>m>>q;
    for (int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    for (int i=1;i<=n;i++) c=0,dfs(i,0,i);
    build();
    for (int i=1;i<=m;i++) cin>>b[i];
    while (q--){
        int l,r;
        cin>>l>>r;
        int ans=INT_MAX;
        for (int s=2;s<=2;s++){
            int lca=b[l];
            for (int i=l;i<=r;i++){
                lca=query(f[s][lca],f[s][b[i]],s);
            }
            for (int i=l;i<=r;i++){
                int x=b[i];
                while (dis[s][x]>=dis[s][lca] && !vis[x]){
                    vis[x]=1;
                    x=par[s][x];
                }
            }
            int ansx=0;
            for (int i=1;i<=n;i++) ansx+=vis[i],vis[i]=0;
            ans=min(ansx,ans);
            //cout<<ansx<<' ';
        }cout<<ans<<endl;
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6612 KB Output is correct
4 Correct 8 ms 37408 KB Output is correct
5 Correct 12 ms 47452 KB Output is correct
6 Correct 7 ms 35164 KB Output is correct
7 Correct 7 ms 41308 KB Output is correct
8 Correct 22 ms 59996 KB Output is correct
9 Correct 12 ms 62044 KB Output is correct
10 Correct 11 ms 62296 KB Output is correct
11 Correct 11 ms 62124 KB Output is correct
12 Correct 12 ms 62044 KB Output is correct
13 Correct 11 ms 62184 KB Output is correct
14 Correct 11 ms 62044 KB Output is correct
15 Correct 10 ms 62040 KB Output is correct
16 Correct 10 ms 62044 KB Output is correct
17 Correct 10 ms 62348 KB Output is correct
18 Correct 10 ms 62044 KB Output is correct
19 Correct 11 ms 62216 KB Output is correct
20 Correct 10 ms 62044 KB Output is correct
21 Correct 10 ms 62136 KB Output is correct
22 Correct 10 ms 62044 KB Output is correct
23 Correct 10 ms 62120 KB Output is correct
24 Correct 10 ms 62044 KB Output is correct
25 Correct 10 ms 62044 KB Output is correct
26 Correct 10 ms 62180 KB Output is correct
27 Correct 2 ms 6744 KB Output is correct
28 Correct 10 ms 62044 KB Output is correct
29 Correct 10 ms 62176 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6612 KB Output is correct
4 Correct 8 ms 37408 KB Output is correct
5 Correct 12 ms 47452 KB Output is correct
6 Correct 7 ms 35164 KB Output is correct
7 Correct 7 ms 41308 KB Output is correct
8 Correct 22 ms 59996 KB Output is correct
9 Correct 12 ms 62044 KB Output is correct
10 Correct 11 ms 62296 KB Output is correct
11 Correct 11 ms 62124 KB Output is correct
12 Correct 12 ms 62044 KB Output is correct
13 Correct 11 ms 62184 KB Output is correct
14 Correct 11 ms 62044 KB Output is correct
15 Correct 10 ms 62040 KB Output is correct
16 Correct 10 ms 62044 KB Output is correct
17 Correct 10 ms 62348 KB Output is correct
18 Correct 10 ms 62044 KB Output is correct
19 Correct 11 ms 62216 KB Output is correct
20 Correct 10 ms 62044 KB Output is correct
21 Correct 10 ms 62136 KB Output is correct
22 Correct 10 ms 62044 KB Output is correct
23 Correct 10 ms 62120 KB Output is correct
24 Correct 10 ms 62044 KB Output is correct
25 Correct 10 ms 62044 KB Output is correct
26 Correct 10 ms 62180 KB Output is correct
27 Correct 2 ms 6744 KB Output is correct
28 Correct 10 ms 62044 KB Output is correct
29 Correct 10 ms 62176 KB Output is correct
30 Runtime error 5 ms 8792 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 16 ms 6492 KB Output is correct
4 Runtime error 6 ms 8796 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Runtime error 5 ms 8796 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 15 ms 6616 KB Output is correct
4 Runtime error 5 ms 8796 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6612 KB Output is correct
4 Correct 8 ms 37408 KB Output is correct
5 Correct 12 ms 47452 KB Output is correct
6 Correct 7 ms 35164 KB Output is correct
7 Correct 7 ms 41308 KB Output is correct
8 Correct 22 ms 59996 KB Output is correct
9 Correct 12 ms 62044 KB Output is correct
10 Correct 11 ms 62296 KB Output is correct
11 Correct 11 ms 62124 KB Output is correct
12 Correct 12 ms 62044 KB Output is correct
13 Correct 11 ms 62184 KB Output is correct
14 Correct 11 ms 62044 KB Output is correct
15 Correct 10 ms 62040 KB Output is correct
16 Correct 10 ms 62044 KB Output is correct
17 Correct 10 ms 62348 KB Output is correct
18 Correct 10 ms 62044 KB Output is correct
19 Correct 11 ms 62216 KB Output is correct
20 Correct 10 ms 62044 KB Output is correct
21 Correct 10 ms 62136 KB Output is correct
22 Correct 10 ms 62044 KB Output is correct
23 Correct 10 ms 62120 KB Output is correct
24 Correct 10 ms 62044 KB Output is correct
25 Correct 10 ms 62044 KB Output is correct
26 Correct 10 ms 62180 KB Output is correct
27 Correct 2 ms 6744 KB Output is correct
28 Correct 10 ms 62044 KB Output is correct
29 Correct 10 ms 62176 KB Output is correct
30 Runtime error 5 ms 8792 KB Execution killed with signal 11
31 Halted 0 ms 0 KB -