Submission #793595

#	Time	Username	Problem	Language	Result	Execution time	Memory
793595		vjudge1	Tourism (JOI23_tourism)	C++14	0 / 100	28 ms	7648 KiB

tourism

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e5, NS = 2000 ;
bool flag1 ;
bool us[NS + 1] ;
int n, m, q, c[N + 1], l[N + 1], r[N + 1], p[N + 1] ;
vector<int> v[N + 1] ;
pair<int, int> mn_mx ;
void dfs(int city, int last)
{
    p[city] = last ;
    for(int i : v[city])
    {
        if(i == last)
            continue ;
        dfs(i, city) ;
    }
}
void build_mn_mx()
{
}
signed main()
{
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> m >> q ;
    for(int i = 1 ; i < n ; i++)
    {
        int a, b ;
        cin >> a >> b ;
        if(a != i || b != i + 1)flag1 = 1 ;
        v[a].push_back(b) ;
        v[b].push_back(a) ;
    }
    for(int i = 1 ; i <= m ; i++)
        cin >> c[i] ;
    for(int i = 1 ; i <= q ; i++)
        cin >> l[i] >> r[i] ;
    if(n <= 2000 && m <= 2000 && q <= 2000)
    {
        us[0] = 1 ;
        dfs(1, 0) ;
        for(int i = 1 ; i <= q ; i++)
        {
            int ans = 0 ;
            for(int j = l[i] ; j <= r[i] ; j++)
            {
                int now = c[j] ;
                while(!us[now])
                {
                    ans++ ;
                    us[now] = 1 ;
                    now = p[now] ;
                }
            }
            for(int i = 1 ; i <= n ; i++)
                us[i] = 0 ;
            cout << ans << '\n' ;
        }
        return 0 ;
    }
    if(!flag1)
    {
//        build_mx_mn() ;
    }
    return 0 ;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41