Submission #804731

#	Time	Username	Problem	Language	Result	Execution time	Memory
804731		vjudge1	Bitaro’s Party (JOI18_bitaro)	C++17	7 / 100	2087 ms	419516 KiB

bitaro

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
using namespace std ;
const int N = 1e5 ;
bool us[N + 1] ;
int n, m, q, ans, sz, cnt[N + 1], gr[N + 1], ans1[N + 1] ;
vector<int> v[N + 1], v1[N + 1] ;
vector<pair<int, int>> mx[N + 1] ;
vector<pair<int, int>> mrg(vector<pair<int, int>> a, vector<pair<int, int>> b)
{
    vector<pair<int, int>> c ;
    int uk1 = (int)a.size() - 1, uk2 = (int)b.size() - 1 ;
    while(c.size() < sz && (uk1 >= 0 || uk2 >= 0))
    {
        pair<int, int> mx1 = {-1e9, -1e9} ;
        if(uk1 >= 0)
            mx1 = a[uk1] ;
        if(uk2 >= 0)
            mx1 = max(mx1, b[uk2]) ;
        if(!c.size() || mx1 != c.back())
            c.push_back(mx1) ;
        if(uk1 >= 0 && mx1 == a[uk1])
            uk1-- ;
        else
            uk2-- ;
    }
    reverse(c.begin(), c.end()) ;
    return c ;
}
void mega_bfs()
{
    for (int i = 1; i <= n; i++)
    {
        mx[i].push_back({0, i}) ;
        for(int j : v1[i])
        {
            vector<pair<int, int>> abu ;
            for(pair<int, int> q : mx[j])
                abu.push_back({q.fi + 1, q.se}) ;
            mx[i] = mrg(mx[i], abu) ;
        }
    }
}

int inf = 1e9;

int mega_get_ans(int city)
{
    int ans = -inf;
    for (int i = 1; i <= n; i++) {
        ans1[i] = -inf;
    }
    ans1[city] = 0;
    for (int i = n; i >= 1; i--)
    {
        for(int j : v1[i])
            ans1[j] = max(ans1[j], ans1[i] + 1) ;
        if(!us[i])
            ans = max(ans, ans1[i]) ;
    }
    return max(ans, -1);
}
signed main()
{
    #ifdef zxc
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio( 0 ) ;
    cin.tie( 0 ) ;
    cout.tie( 0 ) ;
    cin >> n >> m >> q ;
    sz = sqrt(n) + 1 ;
    for(int i = 1 ; i <= m ; i++)
    {
        int a, b ;
        cin >> a >> b ;
        v[a].push_back(b) ;
        v1[b].push_back(a) ;
    }
    mega_bfs() ;
    for(int i = 1 ; i <= q ; i++)
    {
        int t, y ;
        cin >> t >> y ;
        int a[y + 1] ;
        for(int j = 1 ; j <= y ; j++)
        {
            cin >> a[j] ;
            us[a[j]] = 1 ;
        }
        if(y < sz)
        {
            int ans = -1;
            for(pair<int, int> j : mx[t])
            {
                if(us[j.se])
                    continue ;
                ans = max(ans, j.fi) ;
            }
            cout << ans << '\n' ;
        }
        else
        {
            cout << mega_get_ans(t) << '\n' ;
        }
        for(int j = 1 ; j <= y ; j++)
            us[a[j]] = 0 ;
    }
    return 0 ;
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<std::pair<int, int> > mrg(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:15:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   15 |     while(c.size() < sz && (uk1 >= 0 || uk2 >= 0))
      |           ~~~~~~~~~^~~~

• Subtask 1: 7 / 7
• Subtask 2: 0 / 7
• Subtask 3: 0 / 86