Submission #418175

#	Time	Username	Problem	Language	Result	Execution time	Memory
418175		ak2006	Bitaro’s Party (JOI18_bitaro)	C++14	0 / 100	2 ms	332 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vvb = vector<vb>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<ll>;
const ll mod = 1e9 + 7,inf = 1e18;
#define pb push_back
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
void setIO()
{
    fast;
    #ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
}
int main()
{
    setIO();
    int n,m,q;
    cin>>n>>m>>q;
    int SQRT = sqrt(n) + 1;
    vvi adj(n + 1),radj(n + 1);
    vector<vector<pair<int,int>>> farthest(n + 1);
    for (int u = 1;u<=n;u++)farthest[u].pb({0,u});
    while (m--){
        int u,v;
        cin>>u>>v;
        adj[u].pb(v),radj[v].pb(u);
    }
    vb vis(n,0);
    for (int u = 1;u<=n;u++){
        for (int v:adj[u]){
            int l = 0,r = 0;
            vector<pair<int,int>>vals;
            while ((l < farthest[u].size() || r < farthest[v].size()) && vals.size() <= SQRT)
            {
                pair<int,int>to;
                if (l >= farthest[u].size()){
                    to = {farthest[v][r].first,farthest[v][r].second};
                    r++;
                }
                else if (r >= farthest[v].size()){
                    to = {farthest[u][l].first + 1,farthest[u][l].second};
                    l++;
                }
                else if (farthest[u][l].first + 1 >= farthest[v][r].first){
                    to = {farthest[u][l].first + 1,farthest[u][l].second};
                    l++;
                }
                else {
                    to = {farthest[v][r].first,farthest[v][r].second};
                    r++;
                }
                vis[to.second] = 1;
                while (l < farthest[u].size() && vis[farthest[u][l].second])l++;
                while (r < farthest[v].size() && vis[farthest[v][r].second])r++;
                vals.pb(to);
            }
            for (auto &i:vals)vis[i.second] = 0;
            farthest[v] = vals;
        }
    }
    while (q--){
        int target,y;
        cin>>target>>y;
        vb is(n + 1,false);
        for (int i = 0;i<y;i++){
            int x;
            cin>>x;
            is[x] = 1;
        }
        if (y < SQRT){
            bool done = false;
            for (auto it:farthest[target]){
                if (!is[it.second]){
                    cout<<it.first<<'\n';
                    done = true;
                    break;
                }
            }
            if (!done)cout<<-1<<'\n';
        }
        else{
            vl dp(n + 1,-inf);
            ll ans = -1;
            dp[target] = 0;
            if (!is[target])ans = 0;
            for (int u = target - 1;u>=1;u--){
                for (int v:adj[u])dp[u] = max(dp[u],dp[v] + 1);
                if (!is[u])ans = max(ans,dp[u]);
            }
            cout<<ans<<'\n';
        }
    }
    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             while ((l < farthest[u].size() || r < farthest[v].size()) && vals.size() <= SQRT)
      |                     ~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:40:49: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |             while ((l < farthest[u].size() || r < farthest[v].size()) && vals.size() <= SQRT)
      |                                               ~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:40:86: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |             while ((l < farthest[u].size() || r < farthest[v].size()) && vals.size() <= SQRT)
      |                                                                          ~~~~~~~~~~~~^~~~~~~
bitaro.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                 if (l >= farthest[u].size()){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:47:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |                 else if (r >= farthest[v].size()){
      |                          ~~^~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:60:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |                 while (l < farthest[u].size() && vis[farthest[u][l].second])l++;
      |                        ~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp:61:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |                 while (r < farthest[v].size() && vis[farthest[v][r].second])r++;
      |                        ~~^~~~~~~~~~~~~~~~~~~~
bitaro.cpp: In function 'void setIO()':
bitaro.cpp:17:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:18:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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