Submission #800700

#	Time	Username	Problem	Language	Result	Execution time	Memory
800700		ZHIRDILBILDIZ	Bitaro’s Party (JOI18_bitaro)	C++14	14 / 100	1604 ms	418088 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] ;
deque<int> d ;
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()
{
    int uk = 0 ;
    while(uk < d.size())
    {
        int city = d[uk] ;
        for(int i : v1[city])
        {
            cnt[i]++ ;
            if(cnt[i] != v[i].size())
                continue ;
            d.push_back(i) ;
        }
        uk++ ;
    }
    reverse(d.begin(), d.end()) ;
    for(int i : d)
    {
        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) ;
        }
    }
}
void mega_get_ans(int city)
{
    d.clear() ;
    for(int i = 1 ; i <= n ; i++)
        gr[i] = cnt[i] = ans1[i] = 0 ;
    d.push_back(city) ;
    while(d.size())
    {
        int now = d[0] ;
        d.pop_front() ;
        for(int j : v1[now])
        {
            gr[j]++ ;
            if(gr[j] != 1)
                continue ;
            d.push_back(j) ;
        }
    }
    int uk = 0 ;
    d.push_back(city) ;
    while(uk < d.size())
    {
        int city = d[uk] ;
        for(int i : v1[city])
        {
            cnt[i]++ ;
            if(cnt[i] != gr[i])
                continue ;
            d.push_back(i) ;
        }
        uk++ ;
    }
    for(int i : d)
    {
        for(int j : v1[i])
            ans1[j] = max(ans1[j], ans1[i] + 1) ;
        if(!us[i])
            ans = max(ans, ans1[i]) ;
    }
}
signed main()
{
    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) ;
    }
    for(int i = 1 ; i <= n ; i++)
        if(!v[i].size())
            d.push_back(i) ;
    mega_bfs() ;
    for(int i = 1 ; i <= q ; i++)
    {
        ans = -1 ;
        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)
        {
            for(pair<int, int> j : mx[t])
            {
                if(us[j.se])
                    continue ;
                ans = max(ans, j.fi) ;
            }
            cout << ans << '\n' ;
        }
        else
        {
            mega_get_ans(t) ;
            cout << ans << '\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:16: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]
   16 |     while(c.size() < sz && (uk1 >= 0 || uk2 >= 0))
      |           ~~~~~~~~~^~~~
bitaro.cpp: In function 'void mega_bfs()':
bitaro.cpp:36:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while(uk < d.size())
      |           ~~~^~~~~~~~~~
bitaro.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |             if(cnt[i] != v[i].size())
      |                ~~~~~~~^~~~~~~~~~~~~~
bitaro.cpp: In function 'void mega_get_ans(int)':
bitaro.cpp:81:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |     while(uk < d.size())
      |           ~~~^~~~~~~~~~

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