oj.uz

Submission #145538

# Submission time Handle Problem Language Result Execution time Memory
145538 2019-08-20T11:10:15 Z Blagojce Min-max tree (BOI18_minmaxtree) C++11
22 / 100
 536 ms 21752 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x),end(x)

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
ll const inf = 1e9;
ll const mod = 1e9 + 7;
ld const eps = 1e-9;

int n;
vector <int> g[70004];

int sparse[700004][20];
int mquery[700004][20];
int depth[700004];
void dfs(int u, int p){
        sparse[u][0] = p;
        mquery[u][0] = inf;
        fr(i, 1, 20){
                sparse[u][i] = sparse[sparse[u][i - 1]][i - 1];
                mquery[u][i] = inf;
        }
        for(auto e : g[u]){
                if(e != p){
                        depth[e] = depth[u] + 1;
                        dfs(e, u);
                }
        }
}

int lca(int a, int b){
        int mind = min(depth[a], depth[b]);
        for(int i = 19; i >= 0; i --){
                if(depth[sparse[a][i]] >= mind) a = sparse[a][i];
                if(depth[sparse[b][i]] >= mind) b = sparse[b][i];
        }
        if(a == b) return a;
        for(int i = 19; i >= 0; i --){
                if(sparse[a][i] != sparse[b][i]){
                        a = sparse[a][i];
                        b = sparse[b][i];
                }
        }
        return sparse[a][0];
}

int update(int x, int y, int z){
        int p = lca(x, y);
        int l1 = depth[x] - depth[p];
        int l2 = depth[y] - depth[p];
        for(int i = 19; i >= 0; i --){
                if(depth[x] - depth[p] >= (1 << i)){
                        mquery[x][i] = min(mquery[x][i], z);
                        x = sparse[x][i];
                }
        }
        for(int i = 19; i >= 0; i --){
                if(depth[y] - depth[p] >= (1 << i)){
                        mquery[y][i] = min(mquery[y][i], z);
                        y = sparse[y][i];
                }
        }
}
void UPDATE(){
        for(int i = 19; i > 0; i --){
                fr(x, 0, n){
                        mquery[x][i - 1] = min(mquery[x][i - 1], mquery[x][i]);
                        mquery[sparse[x][i - 1]][i - 1] = min(mquery[sparse[x][i - 1]][i - 1], mquery[x][i]);
                }
        }
}
void input(){
        cin >> n;
        fr(i, 0, n - 1){
                int a, b;
                cin >> a >> b;
                --a, --b;
                g[a].pb(b);
                g[b].pb(a);
        }
        dfs(0, 0);
        int k;
        cin >> k;
        fr(i, 0, k){
                char t;
                cin >> t;
                int x, y, z;
                cin >> x >> y >> z;
                --x, --y;
                update(x, y, z);
        }
        UPDATE();
        fr(i, 1, n){
                cout << i + 1 <<' '<<sparse[i][0] + 1 << ' '<<mquery[i][0] << endl;
        }

}
int main()
{
        input();
        return 0;
}

Compilation message

minmaxtree.cpp: In function 'int update(int, int, int)':
minmaxtree.cpp:56:13: warning: unused variable 'l1' [-Wunused-variable]
         int l1 = depth[x] - depth[p];
             ^~
minmaxtree.cpp:57:13: warning: unused variable 'l2' [-Wunused-variable]
         int l2 = depth[y] - depth[p];
             ^~
minmaxtree.cpp:70:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 7.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 21320 KB Output is correct
2 Correct 507 ms 19132 KB Output is correct
3 Correct 517 ms 20216 KB Output is correct
4 Correct 536 ms 21752 KB Output is correct
5 Correct 515 ms 20028 KB Output is correct
6 Correct 523 ms 19676 KB Output is correct
7 Correct 501 ms 19308 KB Output is correct

Subtask #3
0 / 29.0

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

Subtask #4
0 / 42.0

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