oj.uz

Submission #218887

# Submission time Handle Problem Language Result Execution time Memory
218887 2020-04-03T03:18:00 Z Lawliet Islands (IOI08_islands) C++17
80 / 100
 564 ms 131076 KB 
#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

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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 47360 KB Output is correct
2 Correct 32 ms 47352 KB Output is correct
3 Correct 33 ms 47360 KB Output is correct
4 Correct 32 ms 47360 KB Output is correct
5 Correct 32 ms 47352 KB Output is correct
6 Correct 33 ms 47360 KB Output is correct
7 Correct 32 ms 47360 KB Output is correct
8 Correct 34 ms 47360 KB Output is correct
9 Correct 32 ms 47360 KB Output is correct
10 Correct 33 ms 47360 KB Output is correct
11 Correct 32 ms 47360 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47488 KB Output is correct
2 Correct 35 ms 47480 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 47488 KB Output is correct
2 Correct 36 ms 47744 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 48888 KB Output is correct
2 Correct 57 ms 50936 KB Output is correct
3 Correct 47 ms 49400 KB Output is correct
4 Correct 41 ms 48384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 52472 KB Output is correct
2 Correct 84 ms 56868 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 67188 KB Output is correct
2 Correct 164 ms 68684 KB Output is correct
3 Correct 180 ms 74352 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 268 ms 84684 KB Output is correct
2 Correct 315 ms 98800 KB Output is correct
3 Correct 341 ms 100504 KB Output is correct
4 Correct 413 ms 114780 KB Output is correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 452 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 564 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -