제출 #1156371

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1156371		Sam_arvandi	Bitaro’s Party (JOI18_bitaro)	C++20	0 / 100	5 ms	7496 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];
int t[mn];
vector<int> y[mn];
pii ans[mn][msq];
int p[mn], dp[mn], out[mn];
bool mark[mn];
int n;

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

int get(int ind)
{
     int u = t[ind];
     int siz = y[ind].size();
     for(auto v: y[ind]) mark[v] = 1;
     FOR(i, 1, u)
     {
	  int maxi;
	  if (mark[i]) maxi = -1;
	  else maxi = 0;
	  for(auto v: a[i])
	  {
	       maxi = max(maxi, dp[v]);
	  }
	  dp[i] = maxi;
     }
     int tmp = dp[u];
     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);
     }
     int tmp;
     FOR(i, 1, q)
     {
	  cin >> t[i] >> tmp;
	  FOR(j, 1, tmp)
	  {
	       cin >> u;
	       y[i].pb(u);
	  }
	  if (tmp >= sq)
	  {
	       out[i] = get(i);
	  }
     }
     FOR(i, 1, n)
     {
	  for(auto v: a[i])
	  {
	       p[v] = 1;
	  }
	  p[i] = 1;
	  mark[0] = 1;
	  FOR(j, 1, sq)
	  {
	       ans[i][j] = mp(-1, 0);
	       if (!mark[i])
	       {
		    ans[i][j] = mp(0, i);
	       }
	       for(auto v: a[i])
	       {
		    while(ans[v][p[v]].second != 0 and mark[ans[v][p[v]].second]) p[v]++;
		    if (ans[v][p[v]].first != -1 and !mark[ans[v][p[v]].second] 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);
		    }
	       }
	       p[ans[i][j].second]++;
	       mark[ans[i][j].second] = 1;
	  }
	  FOR(j, 1, sq)
	  {
	       mark[ans[i][j].second] = 0;
	  }
     }
     FOR(i, 1, q)
     {
	  if (y[i].size() >= sq)
	  {
	       cout << out[i] << "\n";
	       continue;
	  }
	  for(auto v: y[i])
	  {
	       mark[v] = 1;
	  }
	  FOR(j, 1, sq)
	  {
	       if (!mark[ans[t[i]][j].second])
	       {
		    cout << ans[t[i]][j].first << "\n";
		    break;
	       }
	  }
	  for(auto v: y[i])
	  {
	       mark[v] = 0;
	  }
     }





     return 0;
}

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