Submission #800225

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

bitaro

#include <bits/stdc++.h>


using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define fi first
#define se second
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"

const int N = 2e5 + 9 , mod = 1e9 + 7;
ll  d[N] = {} , a[N] = {}, dp[N] = {}, b[N] ,c[N] ,  sq = 330;

vector<ll>v[N] , v1[N] ;
vector<pair<ll,ll>>vc[N];
ll ans = 0;



void merge(int x , int y){
    vector<pair<ll,ll>>m;
    ll l = 0 , r = 0;
    while(m.size() < sq && (l < vc[x].size() || r < vc[y].size())){
        while(l != vc[x].size() && b[vc[x][l].se] == 1) l++;
        while(r != vc[y].size() && b[vc[y][r].se] == 1) r++;
        if(l == vc[x].size() && r == vc[y].size())
            break;
        if((l != vc[x].size() && r != vc[y].size() && vc[x][l].fi > vc[y][l].fi) || r == vc[y].size())
            m.pb(vc[x][l]) , b[vc[x][l].se] = 1 , l++;
        else
            m.pb({vc[y][r].fi + 1 , vc[y][r].se}) , b[vc[y][r].se] = 1, r++;
        }
    vc[x] = m;
    for(auto to : vc[x])
        b[to.se] = 0;
}

void solve(){
    ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
    cin>>n>>m>>q;
    for(i = 1; i <= m; i++){
        cin>>x>>y;
        v[x].pb(y);
        v1[y].pb(x);
    }
    for(i = 1; i <= n; i++)
        vc[i].pb({0 , i});
    for(i = 1; i <= n; i++)
        for(auto to : v[i])
            merge(to , i);
    while(q --){
        cin>>x>>y;
        vector<int>v;
        for(i = 1; i <= y; i++)
            cin>>k , v.pb(k) , b[k] = 1;
        ans = -1;
        if(y < sq){
            for(auto to : vc[x])
                if(b[to.se] == 0)
                    ans = max(ans , to.fi);
        }else{
            for(i = 1; i <= n; i++){
                (b[i] == 0 ? d[i] = 0 : d[i] = -1);
                for(auto to : v1[i])
                    if(d[to] != -1)
                        d[i] = max(d[i] , d[to] + 1);
            }
            ans = max(ans , d[x]);
        }
        cout<<ans<<"\n";
        for(auto to : v)
            b[to] = 0;
    }
}

int main(){

     TL;
     /*
     #ifndef ONLINE_JUDGE
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
     #endif
     */
int t = 1;
//cin>>t;

while(t--)
     {
     solve();
     }

}
// Author : حسن

Compilation message (stderr)

bitaro.cpp: In function 'void merge(int, int)':
bitaro.cpp:35:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   35 |     while(m.size() < sq && (l < vc[x].size() || r < vc[y].size())){
      |           ~~~~~~~~~^~~~
bitaro.cpp:35:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while(m.size() < sq && (l < vc[x].size() || r < vc[y].size())){
      |                             ~~^~~~~~~~~~~~~~
bitaro.cpp:35:51: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     while(m.size() < sq && (l < vc[x].size() || r < vc[y].size())){
      |                                                 ~~^~~~~~~~~~~~~~
bitaro.cpp:36:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         while(l != vc[x].size() && b[vc[x][l].se] == 1) l++;
      |               ~~^~~~~~~~~~~~~~~
bitaro.cpp:37:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         while(r != vc[y].size() && b[vc[y][r].se] == 1) r++;
      |               ~~^~~~~~~~~~~~~~~
bitaro.cpp:38:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if(l == vc[x].size() && r == vc[y].size())
      |            ~~^~~~~~~~~~~~~~~
bitaro.cpp:38:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |         if(l == vc[x].size() && r == vc[y].size())
      |                                 ~~^~~~~~~~~~~~~~~
bitaro.cpp:40:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if((l != vc[x].size() && r != vc[y].size() && vc[x][l].fi > vc[y][l].fi) || r == vc[y].size())
      |             ~~^~~~~~~~~~~~~~~
bitaro.cpp:40:36: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if((l != vc[x].size() && r != vc[y].size() && vc[x][l].fi > vc[y][l].fi) || r == vc[y].size())
      |                                  ~~^~~~~~~~~~~~~~~
bitaro.cpp:40:87: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         if((l != vc[x].size() && r != vc[y].size() && vc[x][l].fi > vc[y][l].fi) || r == vc[y].size())
      |                                                                                     ~~^~~~~~~~~~~~~~~
bitaro.cpp: In function 'void solve()':
bitaro.cpp:51:16: warning: unused variable 'j' [-Wunused-variable]
   51 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                ^
bitaro.cpp:51:28: warning: unused variable 'z' [-Wunused-variable]
   51 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                            ^
bitaro.cpp:51:32: warning: unused variable 's' [-Wunused-variable]
   51 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                ^
bitaro.cpp:51:40: warning: unused variable 'f' [-Wunused-variable]
   51 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                        ^
bitaro.cpp:51:43: warning: unused variable 'l' [-Wunused-variable]
   51 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                           ^
bitaro.cpp:51:47: warning: unused variable 'r' [-Wunused-variable]
   51 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                               ^
bitaro.cpp:51:67: warning: unused variable 'mn' [-Wunused-variable]
   51 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                                                   ^~
bitaro.cpp:51:80: warning: unused variable 'mx' [-Wunused-variable]
   51 |     ll q , i , j , m , n,  z , s  = 0, f, l , r , k , x = 0 , y , mn  = 1e18 , mx = -1;
      |                                                                                ^~

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