Submission #1177849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177849		vukhacminh	Bitaro’s Party (JOI18_bitaro)	C++20	14 / 100	2098 ms	115608 KiB

bitaro

/**
*    Author :  Vu Khac Minh
*    Created : 08.03.2024
**/
#include <bits/stdc++.h>
#define MASK(x) ((1ll) << (x))
#define BIT(x, i) (((x) >> (i)) & (1))
#define c_bit(i) __builtin_popcountll(i) 
#define SET_ON(x, i) ((x) | MASK(i)) 
#define SET_OFF(x, i) ((x) & ~MASK(i)) 
#define ALL(v) (v).begin(), (v).end()
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define db(val) "["#val" = " << (val) << "] "
#define ll long long
using namespace std;
const int maxn = 2e5 + 5;
const int mod = 1e9+7;
void file()
{
    #define Task "ROUNDPRI"
    if(fopen(Task".inp","r"))
    {
        freopen(Task".inp","r",stdin);
        freopen(Task".out","w",stdout);
    }
}
vector<pair<int,int>> dp[maxn];
int n,nquery,m,f[maxn],vis[maxn],b[maxn];
vector<int> adj[maxn];
void solve()
{
        cin>>n>>m>>nquery;
        FOR(i,1,m)
        {
            int u,v;
            cin>>u>>v;
            adj[v].push_back(u);
        }
        FOR(i,1,n)
        {
            vector<pair<int,int>> save;
            save.push_back({0,i});
            for(auto u : adj[i])
                for(auto v : dp[u])
                {
                    save.push_back({v.first+1,v.second});
                }
            sort(ALL(save),greater<pair<int,int>>());
            for(auto x : save)
            if(vis[x.second] == 0 && dp[i].size() <=100) 
            {
                    dp[i].push_back({x.first,x.second});
                    vis[x.second] = 1;
            }
            for(auto x: save) vis[x.second] = 0;
        }
    while(nquery--)
    {
        int pos,k,x,res=-1;
        cin>>pos>>k;
            FOR(i,1,k)
            {
                cin>>b[i];
                vis[b[i]] = 1;
            }
        if(dp[pos].size() <= 100)
        {
                for(auto u : dp[pos])
                    if(!vis[u.second]) res  =max(res,u.first);
        }else
        {
            FORD(i,pos,1) f[i] = -1;
            f[pos] = 0;
            FORD(i,pos,1)
            {
                if(f[i]!=-1)
                {
                    if(!vis[i]) res = max(res,f[i]);
                    for(auto u : adj[i])
                        f[u] = max(f[u],f[i] +1);
                }
            }
        }
        FOR(i,1,k) vis[b[i]] = 0;
        cout<<res<<'\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    file();
    //cin >> ntest;
    while (ntest--)
    {
        solve();
    }

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'void file()':
bitaro.cpp:25:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:26:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         freopen(Task".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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