oj.uz

Submission #704113

# Submission time Handle Problem Language Result Execution time Memory
704113 2023-03-01T15:33:11 Z 1075508020060209tc Unique Cities (JOI19_ho_t5) C++14
4 / 100
 2000 ms 39020 KB 
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define X first
#define Y second
int n;int m;
int ar[500005];
vector<int>e[500005];
vector<int>freq[500005];
int dph[500005];

void dfs(int nw,int pa){
dph[nw]=dph[pa]+1;
freq[dph[nw]].push_back(nw);
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    if(v==pa){continue;}
    dfs(v,nw);
}
}


void solve(int rt){
dfs(rt,0);
set<int>st;
for(int i=2;i<=n;i++){
    if(freq[i].size()==1){
        st.insert(ar[freq[i][0]]);
    }
    freq[i].clear();
}
cout<<st.size()<<endl;
}



signed main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
    int a;int b;
    cin>>a>>b;
    e[a].push_back(b);
    e[b].push_back(a);
}
for(int i=1;i<=n;i++){
    cin>>ar[i];
}
for(int i=1;i<=n;i++){
    solve(i);
}



}

Compilation message

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

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Output is correct
2 Correct 82 ms 24016 KB Output is correct
3 Correct 75 ms 23948 KB Output is correct
4 Correct 105 ms 24232 KB Output is correct
5 Correct 97 ms 24024 KB Output is correct
6 Correct 150 ms 24080 KB Output is correct
7 Correct 127 ms 24140 KB Output is correct
8 Correct 96 ms 24012 KB Output is correct
9 Correct 105 ms 24168 KB Output is correct
10 Correct 110 ms 24284 KB Output is correct
11 Correct 121 ms 24072 KB Output is correct
12 Correct 76 ms 24016 KB Output is correct
13 Correct 150 ms 24244 KB Output is correct
14 Correct 120 ms 25688 KB Output is correct
15 Correct 114 ms 25500 KB Output is correct
16 Correct 64 ms 23892 KB Output is correct
17 Correct 130 ms 29440 KB Output is correct
18 Correct 110 ms 26040 KB Output is correct
19 Correct 100 ms 24008 KB Output is correct
20 Correct 317 ms 24136 KB Output is correct
21 Correct 144 ms 24320 KB Output is correct
22 Correct 95 ms 24052 KB Output is correct
23 Correct 108 ms 24060 KB Output is correct
24 Correct 105 ms 24124 KB Output is correct
25 Correct 104 ms 24056 KB Output is correct
26 Correct 71 ms 24024 KB Output is correct
27 Correct 230 ms 24104 KB Output is correct
28 Correct 196 ms 29004 KB Output is correct
29 Correct 125 ms 25852 KB Output is correct
30 Correct 60 ms 23980 KB Output is correct
31 Correct 162 ms 29488 KB Output is correct
32 Correct 160 ms 25964 KB Output is correct

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2053 ms 35504 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 32.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2055 ms 39020 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23800 KB Output is correct
2 Correct 82 ms 24016 KB Output is correct
3 Correct 75 ms 23948 KB Output is correct
4 Correct 105 ms 24232 KB Output is correct
5 Correct 97 ms 24024 KB Output is correct
6 Correct 150 ms 24080 KB Output is correct
7 Correct 127 ms 24140 KB Output is correct
8 Correct 96 ms 24012 KB Output is correct
9 Correct 105 ms 24168 KB Output is correct
10 Correct 110 ms 24284 KB Output is correct
11 Correct 121 ms 24072 KB Output is correct
12 Correct 76 ms 24016 KB Output is correct
13 Correct 150 ms 24244 KB Output is correct
14 Correct 120 ms 25688 KB Output is correct
15 Correct 114 ms 25500 KB Output is correct
16 Correct 64 ms 23892 KB Output is correct
17 Correct 130 ms 29440 KB Output is correct
18 Correct 110 ms 26040 KB Output is correct
19 Correct 100 ms 24008 KB Output is correct
20 Correct 317 ms 24136 KB Output is correct
21 Correct 144 ms 24320 KB Output is correct
22 Correct 95 ms 24052 KB Output is correct
23 Correct 108 ms 24060 KB Output is correct
24 Correct 105 ms 24124 KB Output is correct
25 Correct 104 ms 24056 KB Output is correct
26 Correct 71 ms 24024 KB Output is correct
27 Correct 230 ms 24104 KB Output is correct
28 Correct 196 ms 29004 KB Output is correct
29 Correct 125 ms 25852 KB Output is correct
30 Correct 60 ms 23980 KB Output is correct
31 Correct 162 ms 29488 KB Output is correct
32 Correct 160 ms 25964 KB Output is correct
33 Execution timed out 2053 ms 35504 KB Time limit exceeded
34 Halted 0 ms 0 KB -