oj.uz

Submission #1103672

# Submission time Handle Problem Language Result Execution time Memory
1103672 2024-10-21T14:06:11 Z Ahmed57 Tree (IOI24_tree) C++17
18 / 100
 87 ms 28580 KB 
#include <bits/stdc++.h>
using namespace std;
long long cnt = 0;
bool nah = 0;
int root = -1;
int w[200001];
int deg[200001];
vector<int> adj[200001];
vector<int> na,pref;
int dfs(int i,int pr){
    int c1 = 0;
    for(auto j:adj[i]){
        if(j==pr)continue;
        int x = dfs(j,i);
        if(w[i]==0){
            na.push_back(x);
        }
        c1+=x;
    }
    if((adj[i].size()==1&&root!=i)||w[i]==0){
        c1 = 1;
    }
    return c1;
}
void init(std::vector<int> P, std::vector<int> W){
    if(P.size()==1){
        nah = 1;
    }
    for(int i = 0;i<P.size();i++){
        w[i] = W[i];
        int x = P[i];
        if(x==-1){
            root = i;
        }else{
            adj[i].push_back(x);
            adj[x].push_back(i);
            deg[x]++;
            deg[i]++;
        }
    }
    for(int i = 0;i<P.size();i++){
        if(i==root)continue;
        if(deg[i]==1&&w[i])cnt++;
    }
    na.push_back(dfs(root,-1));
    sort(na.begin(),na.end());
    int xx = 0;
    for(int i = 0;i<na.size();i++){
        xx+=na[i];
        pref.push_back(xx);
    }
}
long long query(int L, int R){
    if(nah)return (w[0]==0?0:L);
    long long all = cnt*L;
    int it = lower_bound(na.begin(),na.end(),(R+L-1)/L)-na.begin();
    long long f = pref.back()-(it==0?0:pref[it-1]);
    long long d = pref.size()-it;
    all+=f*L-d*R;
    return all;
}

Compilation message

tree.cpp: In function 'void init(std::vector<int>, std::vector<int>)':
tree.cpp:29:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for(int i = 0;i<P.size();i++){
      |                   ~^~~~~~~~~
tree.cpp:41:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for(int i = 0;i<P.size();i++){
      |                   ~^~~~~~~~~
tree.cpp:48:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0;i<na.size();i++){
      |                   ~^~~~~~~~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 27340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5200 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 28580 KB Output is correct
2 Correct 70 ms 17192 KB Output is correct
3 Correct 73 ms 17192 KB Output is correct
4 Correct 70 ms 17152 KB Output is correct
5 Correct 72 ms 17192 KB Output is correct
6 Correct 69 ms 16936 KB Output is correct
7 Correct 70 ms 17192 KB Output is correct
8 Correct 57 ms 18068 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 28580 KB Output is correct
2 Correct 70 ms 17192 KB Output is correct
3 Correct 73 ms 17192 KB Output is correct
4 Correct 70 ms 17152 KB Output is correct
5 Correct 72 ms 17192 KB Output is correct
6 Correct 69 ms 16936 KB Output is correct
7 Correct 70 ms 17192 KB Output is correct
8 Correct 57 ms 18068 KB Output is correct
9 Correct 80 ms 24100 KB Output is correct
10 Correct 80 ms 21040 KB Output is correct
11 Correct 87 ms 21044 KB Output is correct
12 Correct 78 ms 21032 KB Output is correct
13 Correct 75 ms 20928 KB Output is correct
14 Correct 81 ms 20932 KB Output is correct

Subtask #6
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 63 ms 27296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4944 KB Output is correct
2 Incorrect 52 ms 27340 KB Output isn't correct
3 Halted 0 ms 0 KB -