Submission #55933

# Submission time Handle Problem Language Result Execution time Memory
55933 2018-07-09T07:49:03 Z 정원준(#1565) Telegraph (JOI16_telegraph) C++11
0 / 100
13 ms 12152 KB
#include <bits/stdc++.h>
#define L long long


using namespace std;

L n;
L costsum,cyclecost,macost,sum[100010];

vector<L>v[100010],c[100010],u[100010],vdirec[100010],cdirec[100010];

L chk[100010],cycle[100010];


L dfs(L x){
	//printf("1: %lld ",x);
	L i,ret=0;
	for(i=0;i<vdirec[x].size();i++)
	{
		if(!chk[vdirec[x][i]])
		{
			chk[vdirec[x][i]]=1;
			cycle[x]|=dfs(vdirec[x][i]);
		}
		else cycle[x]=1;
	}
	return cycle[x];
}

L dfs2(L x){
	L i;
//	printf("2 %lld\n",x);
	for(i=0;i<vdirec[x].size();i++)
	{
		if(chk[vdirec[x][i]]!=2)
		{
			chk[vdirec[x][i]]=2;
			dfs2(vdirec[x][i]);
			sum[x]+=sum[vdirec[x][i]]+cdirec[x][i];
			//printf("%lld ",vdirec[x][i]);
		}
	//	puts("");
		
		if(!cycle[x]||cycle[vdirec[x][i]])
		{
			cyclecost+=cdirec[x][i];
		}
	}
}

L dfs3(L x){
	L i,temp=0,ret=0;
	for(i=0;i<vdirec[x].size();i++)
	{
		if(chk[vdirec[x][i]]!=3&&cycle[vdirec[x][i]])
		{
			chk[vdirec[x][i]]=3;
			dfs3(vdirec[x][i]);
		}
		if(cycle[vdirec[x][i]]) temp-=cdirec[x][i];
	}
	//printf("%lld\n",x);
			//printf("%lld %lld\n",cyclecost,temp);
	macost=max(macost,cyclecost+temp);
	for(i=0;i<vdirec[x].size();i++)
	{
		if(!cycle[vdirec[x][i]])
		{
			temp+=cdirec[x][i];
			//printf("%lld %lld\n",cyclecost,temp);
			macost=max(macost,cyclecost+temp);
			temp-=cdirec[x][i];
		}
	}
}

L chkall[100010];

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

int main()
{
	scanf("%lld",&n);
	L i;
	for(i=1;i<=n;i++)
	{
		L before,cost;
		scanf("%lld %lld",&before,&cost);
		costsum+=cost;
		v[before].push_back(i);
		c[before].push_back(cost);
	
		u[before].push_back(before);
		v[i].push_back(before);
		c[i].push_back(cost);
		u[i].push_back(before);
		
		vdirec[before].push_back(i);
		cdirec[before].push_back(cost);
	}
	if(cycle_all())
	{
		puts("0");
		return 0;
	}
	for(i=1;i<=n;i++)
	{
		if(!chk[i])
		{
			chk[i]=1;
			if(dfs(i))
			{
				//puts("");
				//printf("%lld ",i);
				chk[i]=2;
				cyclecost=0;
				dfs2(i);
				//printf("%lld\n",cyclecost);
				chk[i]=3;
				macost=0;
				dfs3(i);
				costsum-=macost;
			}
			else
			{
				//puts("");
			}
			
		}
	}
	for(i=1;i<=n;i++)
	{
		//printf("%lld ",sum[i]);
	}
	//puts("");
	for(i=1;i<=n;i++)
	{
		//printf("%lld ",cycle[i]);
	}
	//puts("");
	printf("%lld",costsum);
}

Compilation message

telegraph.cpp: In function 'long long int dfs(long long int)':
telegraph.cpp:18:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vdirec[x].size();i++)
          ~^~~~~~~~~~~~~~~~~
telegraph.cpp:17:6: warning: unused variable 'ret' [-Wunused-variable]
  L i,ret=0;
      ^~~
telegraph.cpp: In function 'long long int dfs2(long long int)':
telegraph.cpp:33:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vdirec[x].size();i++)
          ~^~~~~~~~~~~~~~~~~
telegraph.cpp:49: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:53:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vdirec[x].size();i++)
          ~^~~~~~~~~~~~~~~~~
telegraph.cpp:65:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vdirec[x].size();i++)
          ~^~~~~~~~~~~~~~~~~
telegraph.cpp:52:13: warning: unused variable 'ret' [-Wunused-variable]
  L i,temp=0,ret=0;
             ^~~
telegraph.cpp:75:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
telegraph.cpp: In function 'int main()':
telegraph.cpp:102:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%lld",&n);
  ~~~~~^~~~~~~~~~~
telegraph.cpp:107:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&before,&cost);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12152 KB Output isn't correct
2 Halted 0 ms 0 KB -