| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 55960 |
2018-07-09T08:28:26 Z |
정원준(#1565) |
Telegraph (JOI16_telegraph) |
C++11 |
|
7 ms |
5248 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,plusma=0;
if(cycle[x])
for(i=0;i<v[x].size();i++)
{
if(!chk2[v[x][i]])
{
chk2[v[x][i]]=2;
dfs2(v[x][i]);
}
if(cycle[v[x][i]])
{
cyclesum+=c[x][i];
}
}
else
{
for(i=0;i<v[x].size();i++)
{
if(!chk2[v[x][i]])
{
chk2[v[x][i]]=2;
dfs2(v[x][i]);
}
plusma=max(plusma,c[x][i]);
}
cyclesum+=plusma;
}
}
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()
{
//freopen("input2.txt","r",stdin);
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 %lld %lld\n",i,cyclesum,macost);
}
}
}
for(i=1;i<=n;i++)
{
// printf("%lld ",cycle[i]);
}
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:56:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
telegraph.cpp:70:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
telegraph.cpp:81: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:85:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
telegraph.cpp:100:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(i=0;i<v[x].size();i++)
~^~~~~~~~~~~~
telegraph.cpp:108:1: warning: no return statement in function returning non-void [-Wreturn-type]
}
^
telegraph.cpp: In function 'int main()':
telegraph.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",&n);
~~~~~^~~~~~~~~~~
telegraph.cpp:118: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 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5140 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5156 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5156 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
5248 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5140 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5156 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5156 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
5248 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5140 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5156 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5156 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
5248 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
4984 KB |
Output is correct |
| 2 |
Correct |
6 ms |
5140 KB |
Output is correct |
| 3 |
Correct |
5 ms |
5156 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5156 KB |
Output is correct |
| 5 |
Incorrect |
7 ms |
5248 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
