Submission #218887

#	Time	Username	Problem	Language	Result	Execution time	Memory
218887		Lawliet	Islands (IOI08_islands)	C++17	80 / 100	564 ms	131076 KiB

islands

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;
typedef pair<lli,int> pii;

const int MAXN = 1000010;
const lli INF = 1000000000000000000LL;

int n;

int weight[MAXN];
int degree[MAXN];

lli dp[MAXN];
lli maxProf[MAXN][2];

bool marc[MAXN];

vector< int > adj[MAXN];
vector< int > indEdge[MAXN];

queue< int > q;

void updateIndMx(int& ind, lli& opt, int i, lli val)
{
	if( opt < val )
	{
		ind = i;
		opt = val;
	}
}

void addSon(int cur, int p, int w)
{
	lli val = maxProf[cur][0] + w;

	maxProf[p][1] = max( maxProf[p][1] , val );
	if( maxProf[p][0] < maxProf[p][1] ) swap( maxProf[p][0] , maxProf[p][1] );

	dp[p] = max( dp[p] , dp[cur] );

	degree[p]--;
}

int getNext(int cur)
{
	for(int i = 0 ; i < adj[cur].size() ; i++)
		if( !marc[ indEdge[cur][i] ] ) return i;

	return -1;
}

void topologicalSorting()
{
	for(int i = 1 ; i <= n ; i++)
		if( degree[i] == 1 ) q.push( i );

	while( !q.empty() )
	{
		int cur = q.front();
		q.pop();

		dp[cur] = max( dp[cur] , maxProf[cur][0] + maxProf[cur][1] );

		int e = getNext( cur );

		int father = adj[cur][e];
		int ind = indEdge[cur][e];

		marc[ind] = true;

		addSon( cur , father , weight[ind] );

		if( degree[father] == 1 ) q.push( father ); 
	}
}

lli findDiameter(int cur)
{
	vector< int > cycleNodes;

	vector< lli > sEdges( 1 , 0 );//Prefix sum of the cycle

	lli ans = 0;

	while( true )
	{
		cycleNodes.push_back( cur );

		dp[cur] = max( dp[cur] , maxProf[cur][0] + maxProf[cur][1] );
		ans = max( ans , dp[cur] );//Diameter of the tree

		int e = getNext( cur );

		if( e == -1 ) break;

		int ind = indEdge[cur][e];

		if( marc[ind] ) break;
		marc[ind] = true;

		sEdges.push_back( sEdges.back() + weight[ind] );

		cur = adj[cur][e];
	}

	cycleNodes.pop_back();
	lli weightCycle = sEdges.back();

	int indOptSum;
	int indOptDiff;

	lli optSum = -INF;
	lli optDiff = -INF;

	for(int i = 0 ; i < cycleNodes.size() ; i++)
	{
		int cur = cycleNodes[i];

		lli curSum = maxProf[cur][0] + sEdges[i];
		lli curDiff = maxProf[cur][0] - sEdges[i];

		ans = max( ans , optDiff + curSum );
		ans = max( ans , weightCycle + optSum + curDiff );

		updateIndMx( indOptSum , optSum , i , curSum );
		updateIndMx( indOptDiff , optDiff , i , curDiff );
	}

	return ans;
}

void buildEdge(int U, int V, int i)
{
	adj[U].push_back( V );
	adj[V].push_back( U );

	indEdge[U].push_back( i );
	indEdge[V].push_back( i );
}

int main()
{
	scanf("%d",&n);

	for(int i = 1 ; i <= n ; i++)
	{
		int U;
		scanf("%d %d",&U,&weight[i]);

		buildEdge( U , i , i );
	}

	for(int i = 1 ; i <= n ; i++)
		degree[i] = adj[i].size();

	topologicalSorting();

	lli ans = 0;

	for(int i = 1 ; i <= n ; i++)
		if( !marc[i] ) ans += findDiameter( i );

	printf("%lld\n",ans);
}

Compilation message (stderr)

islands.cpp: In function 'int getNext(int)':
islands.cpp:48:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
islands.cpp: In function 'lli findDiameter(int)':
islands.cpp:117:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < cycleNodes.size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~~~
islands.cpp: In function 'int main()':
islands.cpp:145:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
islands.cpp:150:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&U,&weight[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 33 / 33
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10