Submission #1098824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098824		simona1230	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	4 ms	9816 KiB

necklace

// Online C++ compiler to run C++ program online
#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int x,d;
    edge(){}
    edge(int _x,int _d)
    {
        x=_x;
        d=_d;
    }
};

int n;
int a[200001];
vector<edge> v[200001];
void read()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    
    for(int i=1;i<n;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        v[x].push_back({y,z});
        v[y].push_back({x,z});
    }
}

vector<int> e[200001];
int cnt[200001];
void dfs(int i,int curr,int bg,int p)
{
    for(int j=0;j<v[i].size();j++)
    {
        edge nb=v[i][j];
        if(nb.x==p)continue;
        int d=curr+nb.d;
        if(a[bg]-d>a[nb.x])dfs(nb.x,d,bg,i);
        else 
        {
            cout<<bg<<" "<<nb.x<<endl;
            cnt[nb.x]++,e[bg].push_back(nb.x);
        }
    }
}

int main() {
    read();
    for(int i=1;i<=n;i++)
    {
        dfs(i,0,i,0);
    }
    
    int ans=0;
    
    for(int i=1;i<=n;i++)
        if(cnt[i]==0)ans++;
        
    cout<<ans<<endl;

    return 0;
}

/*
10
1 2 2 2 6 3 4 5 4 3
1 2 5
2 3 1
2 4 5
4 5 2
4 6 4
4 7 3
1 8 1 
8 9 5
8 10 4

1 2
1 8
2 1
2 3
2 4
3 2
4 2
4 5
4 6
4 7
5 2
5 6
5 7
6 4
7 4
8 2
8 9
8 10
9 8
10 8
*/

Compilation message (stderr)

necklace.cpp: In function 'void dfs(int, int, int, int)':
necklace.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |     for(int j=0;j<v[i].size();j++)
      |                 ~^~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40