Submission #1109022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109022		jamesbamber	Bitaro’s Party (JOI18_bitaro)	C++17	100 / 100	711 ms	278472 KiB

bitaro

#include <iostream>
#include <vector>
#include <cassert>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
vector<int>g[110000];
vector<int>rev[110000];
int at[110000][320];
int dist[110000][320];
const int SQ=320;
int tmp_a[330];
int tmp_b[330];
int use[110000];
int z[110000];
int dp[110000];
vector<int> bitaro(int N, int M, int Q, vector<int> S, vector<int> E, vector<int> T, vector<int> Y, vector<vector<int>> C){
	int a=N,b=M,c=Q;
	for(int i=0;i<b;i++){
		int p=S[i],q=E[i];p--;q--;
		g[p].push_back(q);
		rev[q].push_back(p);
	}
	for(int i=0;i<a;i++)for(int j=0;j<320;j++)
		dist[i][j]=-mod;
	for(int i=0;i<a;i++){
		dist[i][0]=0;
		at[i][0]=i;
	}
	for(int i=0;i<a;i++){
		for(int j=0;j<g[i].size();j++){
			int to=g[i][j];
			int left=0;
			int right=0;
			int sz=0;
			while(left<SQ||right<SQ){
				if(sz==SQ)break;
				int S,T;
				if((left==SQ||dist[i][left]<0)&&(right==SQ||dist[to][right]<0))break;
				if(right==SQ||(left<SQ&&dist[i][left]+1>=dist[to][right])){
					S=at[i][left];
					T=dist[i][left]+1;
					left++;
				}else{
					S=at[to][right];
					T=dist[to][right];
					right++;
				}
				if(!use[S]){
					tmp_a[sz]=S;
					tmp_b[sz]=T;
					use[S]=1;
					sz++;
				}
			}
			for(int k=0;k<sz;k++)dist[to][k]=tmp_b[k];
			for(int k=0;k<sz;k++)at[to][k]=tmp_a[k];
			for(int k=0;k<sz;k++)use[tmp_a[k]]=0;
		}
	}

    vector<int> ans;

	for(int i=0;i<c;i++){
		int x=T[i],y=Y[i];
		x--;
		for(int j=0;j<y;j++){
            z[j] = C[i][j];
			z[j]--;
		}
		for(int j=0;j<y;j++){
			use[z[j]]=1;
		}
		if(y<SQ){
			bool ok=false;
			for(int j=0;j<SQ;j++){
				if(dist[x][j]<0)break;
				if(!use[at[x][j]]){
					ok=true;
                    ans.push_back(dist[x][j]);
					break;
				}
			}
			if(!ok)ans.push_back(-1);
		}else{
			for(int j=0;j<a;j++){
				dp[j]=-mod;
			}
			dp[x]=0;
			for(int j=x;j>=0;j--){
				for(int k=0;k<rev[j].size();k++){
					dp[rev[j][k]]=max(dp[rev[j][k]],dp[j]+1);
				}
			}
			int ret=-1;
			for(int j=0;j<a;j++){
				if(!use[j])ret=max(ret,dp[j]);
			}
            ans.push_back(ret);
		}
		for(int j=0;j<y;j++){
			use[z[j]]=0;
		}
	}
    return ans;
}

int main(){
    int N, M, Q;
    std::cin >> N >> M >> Q;

    std::vector<int> S(M), E(M);
    for(int i=0; i<M; i++){
        std::cin >> S[i] >> E[i];
    }

    std::vector<std::vector<int>> C(Q);
    std::vector<int> T(Q), Y(Q);
    for(int i=0; i<Q; i++){
        std::cin >> T[i] >> Y[i];
        C[i].resize(Y[i]);
        for(int j=0; j<Y[i]; j++){
            std::cin >> C[i][j];
        }
    }

    std::vector<int> ans = bitaro(N, M, Q, std::move(S), std::move(E), std::move(T), std::move(Y), std::move(C));
    
    assert(ans.size() == Q);
    for(int &x: ans) std::cout << x << "\n";
}

Compilation message (stderr)

bitaro.cpp: In function 'std::vector<int> bitaro(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<std::vector<int> >)':
bitaro.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |   for(int j=0;j<g[i].size();j++){
      |               ~^~~~~~~~~~~~
bitaro.cpp:110:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for(int k=0;k<rev[j].size();k++){
      |                 ~^~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from bitaro.cpp:15:
bitaro.cpp: In function 'int main()':
bitaro.cpp:148:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  148 |     assert(ans.size() == Q);
      |            ~~~~~~~~~~~^~~~

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