Submission #1514967
Source Code Expand
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstdlib>
#include<queue>
#include<cstring>
using namespace std;
int n,k;
int dist[100010];
bool vis[100010];
int ans[100010];
vector<pair<int,int> >v[100010];
void dij(int st)
{
for(int i=1;i<=n;i++)dist[i]=1e9;
priority_queue<pair<int,int> , vector<pair<int,int> > ,greater<pair<int,int> > >q;
q.push(make_pair(0,0));
memset(vis,false,sizeof(vis));
int s=n+1;
while(s--)
{
while(!q.empty() && (vis[q.top().second] || dist[q.top().second]!=q.top().first))q.pop();
int x=q.top().second;
q.pop();
vis[x]=true;
for(int i=0;i<v[x].size();i++)
{
int y=v[x][i].first,w=v[x][i].second;
if(vis[y])continue;
if(dist[x]+w<dist[y])
{
dist[y]=dist[x]+w;
q.push(make_pair(dist[y],y));
}
}
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[x].push_back(make_pair(y,1));
v[y].push_back(make_pair(x,1));
}
for(int i=1;i<=n;i++)ans[i]=-1;
scanf("%d",&k);
for(int i=1;i<=k;i++)
{
int x,y;
scanf("%d%d",&x,&y);
v[0].push_back(make_pair(x,y));
ans[x]=y;
}
dij(0);
for(int i=1;i<=n;i++)
{
if(ans[i]!=-1 && ans[i]!=dist[i])
{
printf("No");
return 0;
}
ans[i]=dist[i];
}
puts("Yes");
for(int i=1;i<=n;i++)
{
printf("%d\n",ans[i]);
}
return 0;
}
Submission Info
Submission Time |
|
Task |
E - Integers on a Tree |
User |
ASSWECAN |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1390 Byte |
Status |
WA |
Exec Time |
79 ms |
Memory |
9512 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:40:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
./Main.cpp:44:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
^
./Main.cpp:49:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&k);
^
./Main.cpp:53:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&x,&y);
^
Judge Result
Set Name |
sample |
All |
Score / Max Score |
0 / 0 |
0 / 800 |
Status |
|
|
Set Name |
Test Cases |
sample |
sample_01.txt, sample_02.txt, sample_03.txt |
All |
binary_01.txt, binary_02.txt, hand_01.txt, hand_02.txt, hand_03.txt, kary_01.txt, kary_02.txt, kary_03.txt, line_01.txt, line_02.txt, line_03.txt, line_04.txt, line_05.txt, line_06.txt, random0_01.txt, random1_01.txt, random1_02.txt, random1_03.txt, random1_04.txt, random1_05.txt, random1_06.txt, random1_07.txt, random1_08.txt, random2_01.txt, random2_02.txt, random2_03.txt, random2_04.txt, random2_05.txt, random2_06.txt, random3_01.txt, random3_02.txt, random4_01.txt, random4_02.txt, random4_03.txt, sample_01.txt, sample_02.txt, sample_03.txt, star_01.txt, star_02.txt |
Case Name |
Status |
Exec Time |
Memory |
binary_01.txt |
AC |
59 ms |
8472 KB |
binary_02.txt |
AC |
38 ms |
7424 KB |
hand_01.txt |
AC |
2 ms |
2688 KB |
hand_02.txt |
AC |
2 ms |
2688 KB |
hand_03.txt |
AC |
2 ms |
2688 KB |
kary_01.txt |
AC |
40 ms |
8060 KB |
kary_02.txt |
AC |
48 ms |
7864 KB |
kary_03.txt |
AC |
40 ms |
7552 KB |
line_01.txt |
AC |
46 ms |
7164 KB |
line_02.txt |
AC |
40 ms |
7296 KB |
line_03.txt |
AC |
40 ms |
7296 KB |
line_04.txt |
AC |
56 ms |
7516 KB |
line_05.txt |
AC |
32 ms |
6528 KB |
line_06.txt |
AC |
48 ms |
7164 KB |
random0_01.txt |
AC |
62 ms |
8312 KB |
random1_01.txt |
AC |
60 ms |
7936 KB |
random1_02.txt |
AC |
61 ms |
7936 KB |
random1_03.txt |
AC |
61 ms |
7980 KB |
random1_04.txt |
AC |
72 ms |
8312 KB |
random1_05.txt |
AC |
56 ms |
7808 KB |
random1_06.txt |
AC |
56 ms |
7808 KB |
random1_07.txt |
AC |
62 ms |
7936 KB |
random1_08.txt |
AC |
79 ms |
9460 KB |
random2_01.txt |
AC |
51 ms |
7168 KB |
random2_02.txt |
AC |
47 ms |
7168 KB |
random2_03.txt |
AC |
51 ms |
7168 KB |
random2_04.txt |
AC |
56 ms |
7296 KB |
random2_05.txt |
AC |
63 ms |
8312 KB |
random2_06.txt |
AC |
74 ms |
9460 KB |
random3_01.txt |
AC |
51 ms |
7168 KB |
random3_02.txt |
WA |
75 ms |
8312 KB |
random4_01.txt |
AC |
61 ms |
7808 KB |
random4_02.txt |
AC |
61 ms |
7808 KB |
random4_03.txt |
AC |
60 ms |
7808 KB |
sample_01.txt |
AC |
2 ms |
2688 KB |
sample_02.txt |
AC |
2 ms |
2688 KB |
sample_03.txt |
AC |
2 ms |
2688 KB |
star_01.txt |
AC |
54 ms |
9512 KB |
star_02.txt |
AC |
46 ms |
9332 KB |