Submission #879337

#	Time	Username	Problem	Language	Result	Execution time	Memory
879337		hasan2006	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	1526 ms	354196 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 se second
#define fi first
#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 = 3e5 + 9 , mod = 1e9 + 7;
ll   a[N] = {}, b[N] , c[N] , dp[N] , sq = 4e2 , us[N];

vector<int> v1[N] ,  v[N];
vector<pair<int,int>>d[N];

void merge(int x , int y){
    ll l1 = 0 , i , j , m , n , l = 0 ,r , s  = 0 , f , k , mx = 0;
    mx = sq;
    vector<pair<int,int>>d2;
    while(mx--){
        s = 0;
        while(l < d[x].size() && us[d[x][l].se] == 1)
            l++;
        while(l1 < d[y].size() && us[d[y][l1].se] == 1)
            l1++;
        if((l < d[x].size() && l1 < d[y].size() && d[x][l].fi + 1 >= d[y][l1].fi) || (l1 == d[y].size()))
                s = 1;
        if(l1 == d[y].size() && l == d[x].size())
            break;
        if(s == 1){
            d2.pb({d[x][l].fi + 1 , d[x][l].se});
            us[d[x][l].se] = 1;
            l++;
        }else {
            us[d[y][l1].se] = 1;
            d2.pb({d[y][l1].fi , d[y][l1].se});
            l1++;
        }
    }
    for(auto to : d2)
        us[to.se] = 0;
    d[y]  = d2;
}

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

int main(){
int t = 1;
//cin>>t;
while(t--)
     {
     solve();
     }
}
// Author : حسن

Compilation message (stderr)

bitaro.cpp: In function 'void merge(int, int)':
bitaro.cpp:33:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         while(l < d[x].size() && us[d[x][l].se] == 1)
      |               ~~^~~~~~~~~~~~~
bitaro.cpp:35:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         while(l1 < d[y].size() && us[d[y][l1].se] == 1)
      |               ~~~^~~~~~~~~~~~~
bitaro.cpp:37:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if((l < d[x].size() && l1 < d[y].size() && d[x][l].fi + 1 >= d[y][l1].fi) || (l1 == d[y].size()))
      |             ~~^~~~~~~~~~~~~
bitaro.cpp:37:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if((l < d[x].size() && l1 < d[y].size() && d[x][l].fi + 1 >= d[y][l1].fi) || (l1 == d[y].size()))
      |                                ~~~^~~~~~~~~~~~~
bitaro.cpp:37:90: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         if((l < d[x].size() && l1 < d[y].size() && d[x][l].fi + 1 >= d[y][l1].fi) || (l1 == d[y].size()))
      |                                                                                       ~~~^~~~~~~~~~~~~~
bitaro.cpp:39:15: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if(l1 == d[y].size() && l == d[x].size())
      |            ~~~^~~~~~~~~~~~~~
bitaro.cpp:39:35: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         if(l1 == d[y].size() && l == d[x].size())
      |                                 ~~^~~~~~~~~~~~~~
bitaro.cpp:28:17: warning: unused variable 'i' [-Wunused-variable]
   28 |     ll l1 = 0 , i , j , m , n , l = 0 ,r , s  = 0 , f , k , mx = 0;
      |                 ^
bitaro.cpp:28:21: warning: unused variable 'j' [-Wunused-variable]
   28 |     ll l1 = 0 , i , j , m , n , l = 0 ,r , s  = 0 , f , k , mx = 0;
      |                     ^
bitaro.cpp:28:25: warning: unused variable 'm' [-Wunused-variable]
   28 |     ll l1 = 0 , i , j , m , n , l = 0 ,r , s  = 0 , f , k , mx = 0;
      |                         ^
bitaro.cpp:28:29: warning: unused variable 'n' [-Wunused-variable]
   28 |     ll l1 = 0 , i , j , m , n , l = 0 ,r , s  = 0 , f , k , mx = 0;
      |                             ^
bitaro.cpp:28:40: warning: unused variable 'r' [-Wunused-variable]
   28 |     ll l1 = 0 , i , j , m , n , l = 0 ,r , s  = 0 , f , k , mx = 0;
      |                                        ^
bitaro.cpp:28:53: warning: unused variable 'f' [-Wunused-variable]
   28 |     ll l1 = 0 , i , j , m , n , l = 0 ,r , s  = 0 , f , k , mx = 0;
      |                                                     ^
bitaro.cpp:28:57: warning: unused variable 'k' [-Wunused-variable]
   28 |     ll l1 = 0 , i , j , m , n , l = 0 ,r , s  = 0 , f , k , mx = 0;
      |                                                         ^
bitaro.cpp: In function 'void solve()':
bitaro.cpp:58:16: warning: unused variable 'j' [-Wunused-variable]
   58 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
bitaro.cpp:58:26: warning: unused variable 'z' [-Wunused-variable]
   58 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
bitaro.cpp:58:29: warning: unused variable 's' [-Wunused-variable]
   58 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                             ^
bitaro.cpp:58:37: warning: unused variable 'f' [-Wunused-variable]
   58 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
bitaro.cpp:58:56: warning: unused variable 'y' [-Wunused-variable]
   58 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                        ^
bitaro.cpp:58:60: warning: unused variable 'mn' [-Wunused-variable]
   58 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                            ^~

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