oj.uz

Submission #55950

# Submission time Handle Problem Language Result Execution time Memory
55950 2018-07-09T08:11:20 Z 정원준(#1565) Telegraph (JOI16_telegraph) C++11
0 / 100
 6 ms 5112 KB 
#include <bits/stdc++.h>
#define L long long

using namespace std;

L n,costsum;

vector<L>v[100010],c[100010];

L chk[100010],color,chk2[100010],chk3[100010];
L allchk[100010];
L cycle[100010];
L cyclesum,macost;

L cycle_all(){
	L i;
	for(i=1;i<=n;i++)
	{
		if(v[i].size()!=1) return 0;
	}
	L x=1;
	allchk[x]=1;
	while(1)
	{
		if(allchk[v[x][0]]) break;
		else
		{
			allchk[v[x][0]]=1;
			x=v[x][0];
		}
	}
	for(i=1;i<=n;i++)
	{
		if(!allchk[i]) return 0;
	}
	return 1;
}

L dfs(L x){
	L i,ret=0;
	for(i=0;i<v[x].size();i++)
	{
		if(!chk[v[x][i]])
		{
			chk[v[x][i]]=color;
			ret|=dfs(v[x][i]);
		}
		else if(chk[v[x][i]]==color) ret=1;
	}
	return cycle[x]=ret;
}

L dfs2(L x){
	L i;
	for(i=0;i<v[x].size();i++)
	{
		if(!chk2[v[x][i]])
		{
			chk2[v[x][i]]=2;
			dfs2(v[x][i]);
		}
		if(!cycle[x]||cycle[v[x][i]])
		{
			cyclesum+=c[x][i];
		}
	}
}

L dfs3(L x){
	L i,sum=0;
	for(i=0;i<v[x].size();i++)
	{
		if(!chk3[v[x][i]])
		{
			chk3[v[x][i]]=3;
			dfs3(v[x][i]);
		}
		if(cycle[v[x][i]])
		{
			sum-=c[x][i];
		}
	}
	if(cycle[x])
	{
		macost=max(macost,cyclesum+sum);
		for(i=0;i<v[x].size();i++)
		{
			if(!cycle[v[x][i]])
			{
				macost=max(macost,cyclesum+sum+c[x][i]);
			}
		}
	}
}

int main()
{
	scanf("%lld",&n);
	L i;
	for(i=1;i<=n;i++)
	{
		L before,cost;
		scanf("%lld %lld",&before,&cost);
		v[before].push_back(i);
		c[before].push_back(cost);
		costsum+=cost;
	}
	if(cycle_all())
	{
		puts("0");
		return 0;
	}
	for(i=1;i<=n;i++)
	{
		if(!chk[i])
		{
			color++;
			chk[i]=color;
			L temp=dfs(i);
			if(temp==1)
			{
				cyclesum=0;
				chk2[i]=2;
				dfs2(i);
				chk3[i]=3;
				macost=0;
				dfs3(i);
				costsum-=macost;
			}
		}
	}
	printf("%lld",costsum);
}

Compilation message

telegraph.cpp: In function 'long long int dfs(long long int)':
telegraph.cpp:41:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
telegraph.cpp: In function 'long long int dfs2(long long int)':
telegraph.cpp:55:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
telegraph.cpp:67:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
telegraph.cpp: In function 'long long int dfs3(long long int)':
telegraph.cpp:71:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
telegraph.cpp:86:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(i=0;i<v[x].size();i++)
           ~^~~~~~~~~~~~
telegraph.cpp:94:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
telegraph.cpp: In function 'int main()':
telegraph.cpp:98:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
telegraph.cpp:103:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&before,&cost);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -