Submission #1078233

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078233		Marco_Escandon	September (APIO24_september)	C++17	100 / 100	151 ms	23036 KiB

september

//#include "september.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define x first
#define y second
vector<ll> temp,p;
vector<vector<ll>> G;
ll dfs(ll node)
{
	ll asd=temp[node];
	for(auto i:G[node])
		asd=max(asd,dfs(i));
	p[node]=asd;
	return asd;
}
vector<ll> calc(ll n, vector<ll> cad)
{
	for(int i=0; i<cad.size(); i++)
		temp[cad[i]]=i;
	dfs(0);
	return p;
}
int solve(int n, int m, std::vector<int> F, std::vector<std::vector<int>> S) {
	G.clear();temp.clear();p.clear();
	G.resize(n+2);temp.resize(n+2);p.resize(n+2);
	for(int i=1; i<n; i++)
		G[F[i]].push_back(i);
	vector<vector<ll>> cad(m);
	vector<ll> last(n+2);
	for(int i=0; i<m; i++)
	{
		cad[i]=calc(n,S[i]);
		for(int j=0; j<S[i].size(); j++)
		{
			last[S[i][j]]=max(j,last[S[i][j]]);
		}
	}
		
	ll a=-1,cont=0;
	for(int i=0; i<S[0].size(); i++)
	{
		if(i>a) cont++;
		for(int j=0; j<m; j++)
		{
			a=max(cad[j][S[j][i]],a);
			a=max(last[S[j][i]]  ,a);
		}
		
	}
	return cont;
}

Compilation message (stderr)

september.cpp: In function 'std::vector<int> calc(ll, std::vector<int>)':
september.cpp:19:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |  for(int i=0; i<cad.size(); i++)
      |               ~^~~~~~~~~~~
september.cpp: In function 'int solve(int, int, std::vector<int>, std::vector<std::vector<int> >)':
september.cpp:34:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int j=0; j<S[i].size(); j++)
      |                ~^~~~~~~~~~~~
september.cpp:41:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |  for(int i=0; i<S[0].size(); i++)
      |               ~^~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 5 / 5
• Subtask 4: 9 / 9
• Subtask 5: 5 / 5
• Subtask 6: 11 / 11
• Subtask 7: 9 / 9
• Subtask 8: 11 / 11
• Subtask 9: 9 / 9
• Subtask 10: 16 / 16