Submission #56694

#	Time	Username	Problem	Language	Result	Execution time	Memory
56694		khsoo01	Bitaro’s Party (JOI18_bitaro)	C++11	100 / 100	1820 ms	211152 KiB

bitaro

#include<bits/stdc++.h>
#define X first
#define Y second
using namespace std;
typedef pair<int,int> pii;

const int N = 100005, X = 255, inf = 1e9;

int n, m, q, o, k, b[N], opt[N];
bool vis[N];

vector<int> adj[N], usd;
vector<pii> dt[N];

void upd (vector<pii> &V, const pii &T) {
	V.push_back(T);
	vis[T.Y] = true;
	usd.push_back(T.Y);
}

int main()
{
	scanf("%d%d%d",&n,&m,&q);
	for(int i=1;i<=m;i++) {
		int A, B;
		scanf("%d%d",&A,&B);
		adj[B].push_back(A);
	}
	for(int i=1;i<=n;i++) {
		for(auto &T : adj[i]) {
			vector<pii> D;
			int P = dt[i].size(), Q = dt[T].size();
			for(int A=0, B=0; (A<P || B<Q) && D.size()<X; ) {
				if(A != P && vis[dt[i][A].Y]) A++;
				else if(B != Q && vis[dt[T][B].Y]) B++;
				else if(A == P) upd(D, pii(dt[T][B].X+1, dt[T][B].Y));
				else if(B == Q) upd(D, dt[i][A]);
				else upd(D, max(pii(dt[T][B].X+1, dt[T][B].Y), dt[i][A]));
			}
			swap(D, dt[i]);
			for(auto &T : usd) {
				vis[T] = false;
			}
			usd.clear();
		}
		if(dt[i].size() < X) dt[i].push_back({0, i});
	}
	while(q--) {
		scanf("%d%d",&o,&k);
		for(int i=1;i<=k;i++) {
			scanf("%d",&b[i]);
			vis[b[i]] = true;
		}
		if(dt[o].size() < X || k < X) {
			bool F = false;
			for(auto &T : dt[o]) {
				if(vis[T.Y]) continue;
				printf("%d\n",T.X);
				F = true;
				break;
			}
			if(!F) puts("-1");
		}
		else {
			for(int i=1;i<=o;i++) {
				opt[i] = (vis[i] ? -inf : 0);
				for(auto &T : adj[i]) {
					opt[i] = max(opt[i], opt[T] + 1);
				}
			}
			printf("%d\n",(opt[o] < 0 ? -1 : opt[o]));
		}
		for(int i=1;i<=k;i++) {
			vis[b[i]] = false;
		}
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d",&n,&m,&q);
  ~~~~~^~~~~~~~~~~~~~~~~~~
bitaro.cpp:26:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&A,&B);
   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:49:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&o,&k);
   ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:51:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d",&b[i]);
    ~~~~~^~~~~~~~~~~~

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