Submission #1156581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156581		Sam_arvandi	Bitaro’s Party (JOI18_bitaro)	C++20	100 / 100	486 ms	253804 KiB

bitaro

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define mp make_pair
#define IOS ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define FOR(i, j, n) for (int i = j; i<= n; i++)
#define ROF(i, n, j) for (int i = n; i>= j; i--)
#define pb push_back
#define sep cout << "--------" << endl;
const int mn = 1e5 + 5, sq = 300, msq = sq + 10;
vector<int> a[mn];
vector<int> y[mn];
pii ans[mn][msq];
int dp[mn], p[mn];
bool mark[mn];
int n;

void cle()
{
     FOR(i, 1, n)
     {
	  dp[i] = 0;
	  mark[i] = 0;
     }
}

int get(int t, int ind)
{
     int siz = y[ind].size();
     for(auto v: y[ind]) mark[v] = 1;
     FOR(i, 1, t)
     {
	  int maxi;
	  if (mark[i]) maxi = -1;
	  else maxi = 0;
	  for(auto v: a[i])
	  {
	       if (dp[v] == -1) continue;
	       maxi = max(maxi, dp[v]+1);
	  }
	  dp[i] = maxi;
     }
     int tmp = dp[t];
     cle();
     return tmp;
}


int main()
{
     IOS;
     int u, v,m , q;
     cin >> n >> m >> q;
     FOR(i, 1, m)
     {
	  cin >> u >> v;
	  a[v].push_back(u);
     }
     FOR(i, 1, n)
     {
	  FOR(j, 1, sq+1)
	  {
	       ans[i][j] = mp(-1, 0);
	  }
     }
     
     FOR(i, 1, n)
     {
	  for(auto v: a[i])
	  {
	       p[v] = 1;
	  }
	  p[i] = 1;
	  p[0] = 1;
	  FOR(j, 1, sq)
	  {
	       int w = 0;
	       if (p[i] == 1)
	       {
		    ans[i][j] = mp(0, i);
		    w = i;
	       }
	       for(auto v: a[i])
	       {
		    while(ans[v][p[v]].first != -1 and mark[ans[v][p[v]].second]) p[v]++;
		    if (ans[v][p[v]].first != -1 and ans[v][p[v]].first + 1 > ans[i][j].first)
		    {
			 ans[i][j] = mp(ans[v][p[v]].first + 1, ans[v][p[v]].second);
			 w = v;
		    }
	       }
	       p[w]++;
	       mark[ans[i][j].second] = 1;
	  }
	  FOR(j, 1, sq)
	  {
	       mark[ans[i][j].second] = 0;
	  }
     }
     int t, siz;
     FOR(i, 1, q)
     {
	  cin >> t >> siz;
	  FOR(j, 1, siz)
	  {
	       cin >> u;
	       y[i].pb(u);
	  }
	  if (siz >= sq)
	  {
	       cout << get(t, i) << "\n";
	       continue;
	  }
	  for(auto v: y[i])
	  {
	       mark[v] = 1;
	  }
	  FOR(j, 1, sq)
	  {
	       if (!mark[ans[t][j].second])
	       {
		    cout << ans[t][j].first << "\n";
		    break;
	       }
	  }
	  for(auto v: y[i])
	  {
	       mark[v] = 0;
	  }
     }





     return 0;
}

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