| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55933 |
2018-07-09T07:49:03 Z |
정원준(#1565) |
Telegraph (JOI16_telegraph) |
C++11 |
|
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 |
- |
