oj.uz

Submission #834020

# Submission time Handle Problem Language Result Execution time Memory
834020 2023-08-22T10:10:56 Z ttamx Tropical Garden (IOI11_garden) C++14
0 / 100
 7 ms 10056 KB 
#include "garden.h"
#include "gardenlib.h"
#include<bits/stdc++.h>

using namespace std;

const int N=150005;
const int M=300005;
const int D=300000;

int n,p;
vector<int> adj[N];
int dp[2][N][2];
int cnt[2][M];
int cyc[2];

int trav(int t,int u,int s){
	s=min(s,(int)adj[u].size()-1);
	if(dp[t][u][s]!=-2)return dp[t][u][s];
	dp[t][u][s]=-1;
	int v=adj[u][s];
	int res=trav(t,v,adj[v][0]==u);
	if(res!=-1)dp[t][u][s]=res+1;
	return dp[t][u][s];
}

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]){
	n=N,p=P;
	for(int t=0;t<2;t++)for(int i=0;i<n;i++)dp[t][i][0]=dp[t][i][1]=-2;
	for(int i=0;i<M;i++){
		int u=R[i][0],v=R[i][1];
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	dp[0][p][0]=dp[1][p][1]=0;
	for(int t=0;t<=adj[p].size();t++){
		for(int i=0;i<n;i++){
			int res=trav(t,i,0);
			if(res!=-1)cnt[t][res]++;
		}
		cyc[t]=trav(t,adj[p][t],adj[adj[p][0]][t]==p);
		if(cyc[t]!=-1){
			cyc[t]++;
			for(int i=cyc[t];i<=D;i++)cnt[t][i]+=cnt[t][i-cyc[t]];
		}
	}
	for(int i=0;i<Q;i++){
		int ans=0;
		for(int t=0;t<=adj[p].size();t++){
			if(G[i]<=D){
				ans+=cnt[t][G[i]];
			}else if(cyc[t]!=-1){
				int d=G[i]-D;
				d=(d+cyc[t]-1)/cyc[t]*cyc[t];
				ans+=cnt[t][G[i]-d];
			}
		}
		answer(ans);
	}
}

Compilation message

garden.cpp: In function 'void count_routes(int, int, int, int (*)[2], int, int*)':
garden.cpp:36:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |  for(int t=0;t<=adj[p].size();t++){
      |              ~^~~~~~~~~~~~~~~
garden.cpp:49:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int t=0;t<=adj[p].size();t++){
      |               ~^~~~~~~~~~~~~~~

Subtask #1
0 / 49.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 10056 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 10056 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 7 ms 10056 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -