oj.uz

Submission #1098824

# Submission time Handle Problem Language Result Execution time Memory
1098824 2024-10-10T06:36:27 Z simona1230 Necklace (Subtask 1-3) (BOI19_necklace1) C++17
0 / 85
 4 ms 9816 KB 
// 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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9816 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9816 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9816 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -