Submission #1234576

#TimeUsernameProblemLanguageResultExecution timeMemory
1234576Bui_Quoc_CuongBitaro’s Party (JOI18_bitaro)C++20
7 / 100
2090 ms14984 KiB
#include <bits/stdc++.h>
#define ll long long
// #define int long long
#define fi first
#define se second
#define pb push_back
#define vi vector <int>
#define pii pair <int, int>
#define FOR(i, a, b) for(int i = a; i <= (int)b; i++)
#define FORD(i, a, b) for(int i = a; i >= (int)b; i--)
#define ALL(A) A.begin(), A.end()
using namespace std;
const int maxn = 2e5 + 5;
int n, m, q;
vector <int> g[maxn];
vector <pair <int, int>> dp[maxn];
int f[maxn];
int vis[maxn];
signed main(void)
{
    cin.tie(nullptr) -> sync_with_stdio(false);
    #define taskname "kieuoanh"
    if(fopen(taskname".inp", "r"))
    {
        freopen(taskname".inp", "r", stdin); 
        freopen(taskname".out", "w", stdout);
    }
    cin >> n >> m >> q;
    FOR(i,1,m)
    {
    	int u,v; cin>>u>>v;
    	g[v].push_back(u);
    }
    FOR(i,1,n)
    {
    	vector<pair<int,int>> save;
    	save.push_back({0, i});
    	for(int &j : g[i])
    	{
    		for(auto x : dp[j])
			{
				save.push_back(make_pair(x.first + 1, x.second));
			}    			
    	}
    	sort(ALL(save), greater <pair <int, int>> ());
    	for(auto x : save)
    	{
    		int v = x.se;
    		if(vis[v] == 0 && dp[i].size() <= 300)
    		{
    			dp[i].push_back(x);
    			vis[v] = 1;
    		} 
    	}
    	for(auto x : save) vis[x.se] = 0;
    }
	memset(f, - 0x3f, sizeof f);
	while(q--)
	{
		int st, k; cin >> st >> k;
		vector <int> vers;
		FOR(i, 1, k)
		{
			int x; cin >> x;
			vis[x] = 1;
			vers.pb(x);
		}
		if(k <= 300)
		{
			int ans = -1;
			for(auto x : dp[st])
			{
				if(vis[x.se] == 0) ans = max(ans, x.fi);
			}
			cout << ans << "\n";
		} else
		{
			FOR(i,1,st) f[i] = -2e9;
			FOR(i,1,st)
			{
				if(vis[i] == 0) f[i] = 0;
				for(int &j : g[i]) f[i] = max(f[i], f[j] + 1);				
			}
			cout << (f[st] >=0 ? f[st] : -1) << "\n";
		}		
		for(auto x : vers) vis[x] = 0;
	}

    return 0;
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
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(taskname".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(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...