Submission #45034

#	Time	Username	Problem	Language	Result	Execution time	Memory
45034		ikura355	Bitaro’s Party (JOI18_bitaro)	C++14	100 / 100	1257 ms	251408 KiB

bitaro

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define X first
#define Y second
const int maxn = 1e5 + 5;
const int block = 310;
const int inf = maxn+5;
int n,m,q;
vector<int> way[maxn];
int p[maxn], busy[maxn];
bool vis[maxn];
pii rec[maxn][311], temp[311];
int dp[maxn];
void small_init() {
	for(int u=1;u<=n;u++) {
	    for(int i=0;i<block;i++) rec[u][i] = {-inf, 0};
		rec[u][0] = {0, u};
		for(auto v : way[u]) {
            for(int i=0;i<block;i++) temp[i] = {-inf, 0};
			//merge
			int pos,i,j;
			pos = i = j = 0;
			vis[0] = 1;
			while(pos<block && (i<block || j<block)) {
//                printf("\t%d: merge %d and %d : %d or %d\n",pos,u,v,i,j);
				//choose maximum
				if(j>=block || rec[u][i].X > rec[v][j].X+1) {
					if(!vis[rec[u][i].Y]) temp[pos++] = {rec[u][i].X, rec[u][i].Y};
					vis[rec[u][i].Y] = 1;
					++i;
				}
				else {
					if(!vis[rec[v][j].Y]) temp[pos++] = {rec[v][j].X+1, rec[v][j].Y};
					vis[rec[v][j].Y] = 1;
					++j;
				}
			}
			for(int i=0;i<block;i++) vis[rec[u][i].Y] = vis[rec[v][i].Y] = 0;
			for(int i=0;i<block;i++) rec[u][i] = temp[i];
		}
//		printf("dest = %d\n",u);
//		for(int i=0;i<block;i++) printf("\t{%d, %d}\n",rec[u][i].X,rec[u][i].Y);
	}
}
int small_solve(int u) {
    int ans = -1;
    for(int i=0;i<block;i++) {
        if(!busy[rec[u][i].Y]) {
            ans = rec[u][i].X;
            break;
        }
    }
    if(ans<0) return -1;
    return ans;
}
int large_solve(int pos) {
    for(int u=1;u<=pos;u++) {
        if(busy[u]) dp[u] = -inf;
        else dp[u] = 0;
        for(auto v : way[u]) dp[u] = max(dp[u], dp[v]+1);
    }
    if(dp[pos]<0) return -1;
    return dp[pos];
}
int main() {
	scanf("%d%d%d",&n,&m,&q);
	for(int i=0;i<m;i++) {
		int u, v; scanf("%d%d",&u,&v);
		way[v].push_back(u);
	}
	small_init();
	while(q--) {
		int u, k; scanf("%d%d",&u,&k);
		for(int i=0;i<k;i++) scanf("%d",&p[i]);
		for(int i=0;i<k;i++) busy[p[i]] = 1;
		if(k < block) printf("%d\n",small_solve(u));
		else printf("%d\n",large_solve(u));
		for(int i=0;i<k;i++) busy[p[i]] = 0;
	}
}

Compilation message (stderr)

bitaro.cpp: In function 'int main()':
bitaro.cpp:67: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:69:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, v; scanf("%d%d",&u,&v);
             ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:74:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int u, k; scanf("%d%d",&u,&k);
             ~~~~~^~~~~~~~~~~~~~
bitaro.cpp:75:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   for(int i=0;i<k;i++) scanf("%d",&p[i]);
                        ~~~~~^~~~~~~~~~~~

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