oj.uz

답안 #422674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
422674 2021-06-10T10:01:36 Z egekabas Min-max tree (BOI18_minmaxtree) C++14
100 / 100
 462 ms 50640 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, q;
vector<int> g[70009];
int dad[70009][20];
int depth[70009];
void dfs(int v, int prt){
    depth[v] = depth[prt]+1;
    dad[v][0] = prt;
    for(int i = 1; i < 20; ++i)
        dad[v][i] = dad[dad[v][i-1]][i-1];
    for(auto u : g[v])
        if(u != prt)
            dfs(u, v);
}
int lca(int x, int y){
    if(depth[x] < depth[y])
        swap(x, y);
    for(int i = 19; i >= 0; --i)
        if(depth[dad[x][i]] >= depth[y])
            x = dad[x][i];
    if(x == y) return x;
    for(int i = 19; i >= 0; --i)
        if(dad[x][i] != dad[y][i]){
            x = dad[x][i];
            y = dad[y][i];
        }
    return dad[x][0];
}
struct node{
    set<pii> mini;
    set<pii, greater<pii>> fin;
    void add(int v1, int v2){
        mini.insert({v1, v2});
        fin.insert({v2, v1});
    }
    void clear(int d){
        while(fin.size() && fin.begin()->ff >= d){
            mini.erase({fin.begin()->ss, fin.begin()->ff});
            fin.erase(fin.begin());
        }
    }
};
void merge(node &a, node &b){
    if(a.mini.size() < b.mini.size())
        swap(a, b);
    for(auto u : b.mini)
        a.add(u.ff, u.ss);
    b.mini.clear();
    b.fin.clear();
}
node mini[70009];
node maxi[70009];
int p[70009];
pii critval[70009];
void calc(int v, int prt){
    p[v] = prt;
    for(auto u : g[v])
        if(u != prt){
            calc(u, v);
            merge(mini[v], mini[u]);
            merge(maxi[v], maxi[u]);
        }
    mini[v].clear(depth[v]);
    maxi[v].clear(depth[v]);
    critval[v] = {-1,-1};
    if(mini[v].mini.size())
        critval[v].ff = -mini[v].mini.begin()->ff;
    if(maxi[v].mini.size())
        critval[v].ss = maxi[v].mini.begin()->ff;
}
vector<int> posval[70009];
int sz[70009];
int ans[70009];
int done[70009];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n;
    for(int i = 0; i < n-1; ++i){
        int x, y;
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }
    dfs(1, 0);
    cin >> q;
    vector<int> mpp;
    for(int i = 0; i < q; ++i){
        char type;
        int x, y, z;
        cin >> type >> x >> y >> z;
        int d = depth[lca(x, y)];

        if(type == 'M'){
            maxi[x].add(z, d);
            maxi[y].add(z, d);
        }
        else{
            mini[x].add(-z, d);
            mini[y].add(-z, d);
        }
        mpp.pb(z);
    }
    sort(all(mpp));
    mpp.resize(unique(all(mpp))-mpp.begin());

    calc(1, 0);
    for(int i = 2; i <= n; ++i){
        if(critval[i].ff != -1){
            critval[i].ff = lower_bound(all(mpp), critval[i].ff)-mpp.begin();
            posval[critval[i].ff].pb(i);
        }
        if(critval[i].ss != -1){
            critval[i].ss = lower_bound(all(mpp), critval[i].ss)-mpp.begin();
            posval[critval[i].ss].pb(i);
        }
    }   
    set<pii> s;
    for(int i = 0; i < mpp.size(); ++i){
        sz[i] = posval[i].size();
        s.insert({posval[i].size(), i});
    }
    while(s.size()){
        int cur = s.begin()->ss;
        s.erase(s.begin());
        done[cur] = 1;
        int v;
        for(auto u : posval[cur])
            if(ans[u] == 0){
                v = u;
                break;
            }
        if(critval[v].ff != -1 && done[critval[v].ff] == 0){
            s.erase({sz[critval[v].ff], critval[v].ff});
            sz[critval[v].ff]--;
            s.insert({sz[critval[v].ff], critval[v].ff});
        }
        if(critval[v].ss != -1 && done[critval[v].ss] == 0){
            s.erase({sz[critval[v].ss], critval[v].ss});
            sz[critval[v].ss]--;
            s.insert({sz[critval[v].ss], critval[v].ss});
        }
        ans[v] = mpp[cur];
    }
    for(int i = 2; i <= n; ++i){
        cout << i << ' ' << p[i] << ' ';
        if(ans[i])
            cout << ans[i];
        else{
            if(critval[i].ff != -1)
                cout << mpp[critval[i].ff];
            else
                cout << 0;
        }
        cout << '\n';
    }
}

Compilation message

minmaxtree.cpp: In function 'int main()':
minmaxtree.cpp:136:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  136 |     for(int i = 0; i < mpp.size(); ++i){
      |                    ~~^~~~~~~~~~~~
minmaxtree.cpp:4:12: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
    4 | #define ss second
      |            ^~~~~~
minmaxtree.cpp:144:13: note: 'v' was declared here
  144 |         int v;
      |             ^

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16780 KB Output is correct
2 Correct 11 ms 16716 KB Output is correct
3 Correct 11 ms 16716 KB Output is correct
4 Correct 10 ms 16768 KB Output is correct

Subtask #2
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 383 ms 45588 KB Output is correct
2 Correct 369 ms 40764 KB Output is correct
3 Correct 383 ms 41984 KB Output is correct
4 Correct 370 ms 46776 KB Output is correct
5 Correct 363 ms 41516 KB Output is correct
6 Correct 338 ms 41916 KB Output is correct
7 Correct 293 ms 40832 KB Output is correct

Subtask #3
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 31872 KB Output is correct
2 Correct 161 ms 33360 KB Output is correct
3 Correct 177 ms 36280 KB Output is correct
4 Correct 191 ms 38380 KB Output is correct
5 Correct 193 ms 34532 KB Output is correct
6 Correct 200 ms 35584 KB Output is correct
7 Correct 179 ms 34104 KB Output is correct
8 Correct 196 ms 33920 KB Output is correct

Subtask #4
42.0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 16780 KB Output is correct
2 Correct 11 ms 16716 KB Output is correct
3 Correct 11 ms 16716 KB Output is correct
4 Correct 10 ms 16768 KB Output is correct
5 Correct 383 ms 45588 KB Output is correct
6 Correct 369 ms 40764 KB Output is correct
7 Correct 383 ms 41984 KB Output is correct
8 Correct 370 ms 46776 KB Output is correct
9 Correct 363 ms 41516 KB Output is correct
10 Correct 338 ms 41916 KB Output is correct
11 Correct 293 ms 40832 KB Output is correct
12 Correct 165 ms 31872 KB Output is correct
13 Correct 161 ms 33360 KB Output is correct
14 Correct 177 ms 36280 KB Output is correct
15 Correct 191 ms 38380 KB Output is correct
16 Correct 193 ms 34532 KB Output is correct
17 Correct 200 ms 35584 KB Output is correct
18 Correct 179 ms 34104 KB Output is correct
19 Correct 196 ms 33920 KB Output is correct
20 Correct 387 ms 43368 KB Output is correct
21 Correct 378 ms 40768 KB Output is correct
22 Correct 445 ms 40568 KB Output is correct
23 Correct 425 ms 40404 KB Output is correct
24 Correct 430 ms 48160 KB Output is correct
25 Correct 397 ms 50640 KB Output is correct
26 Correct 373 ms 49948 KB Output is correct
27 Correct 434 ms 47804 KB Output is correct
28 Correct 365 ms 44156 KB Output is correct
29 Correct 409 ms 44484 KB Output is correct
30 Correct 383 ms 41332 KB Output is correct
31 Correct 365 ms 41436 KB Output is correct
32 Correct 398 ms 43568 KB Output is correct
33 Correct 430 ms 42148 KB Output is correct
34 Correct 462 ms 42060 KB Output is correct
35 Correct 357 ms 40908 KB Output is correct