oj.uz

답안 #723921

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
723921 2023-04-14T13:03:44 Z sunnat Magic Tree (CEOI19_magictree) C++14
11 / 100
 84 ms 15536 KB 
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
#define int long long

struct node{
    int mx;
    int left;
    int right;
    node(){
        mx = 0;
        left = right = -1;
    }
};

node free_node;
int k;

struct Dynamic_Segment_Tree{
    set<pair<int, int> > t;
    
    Dynamic_Segment_Tree(){
        t.emplace(0, 0);
    }
   
    void Set(int id, int w){
       auto elem = t.lower_bound(make_pair(id+1, 0));
       elem --;
       w += elem->second;
       if(elem->first == id) t.erase(elem);
       t.emplace(id, w);
       elem = t.lower_bound(make_pair(id, w));
       while(true){
            auto nxt = elem;
            nxt ++;
            if(nxt == t.end() || nxt->second > elem->second)
                break;
            t.erase(nxt);
       }
    }
    
    void merge(Dynamic_Segment_Tree&d){
        while(!d.t.empty()){
            auto e = d.t.end();
            e --;
            Set(e->first, e->second);
            d.t.erase(e);            
        }
    }
    void print(){
        cout << "----" << endl;
        for(auto x:t) cout <<x.first << ' ' << x.second << endl;
        cout << "----" << endl;
    }
};

Dynamic_Segment_Tree free_seg_tree;

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, m;
    cin >> n >> m >> k;
    vector<int> seg_id(n, -1);
    vector<Dynamic_Segment_Tree> seg_tree;
    vector<vector<int> > g(n);
    vector<pair<int, int> > q(n, make_pair(-1, -1));
    for(int i = 2, f; i <= n; i ++){
        cin >> f;
        g[f-1].push_back(i-1);
    }
    for(int i = 0, v, d, w; i < m; i ++){
        cin >> v >> d >> w;
        q[v-1] = make_pair(d, w);
    }
    for(int u = n-1; u >= 0; u --){
        if(g[u].empty()){
            if(q[u].first == -1) continue;
            seg_id[u] = seg_tree.size();
            seg_tree.push_back(free_seg_tree);
            seg_tree[seg_id[u]].Set(q[u].first, q[u].second);
        }
        else{
            sort(g[u].begin(), g[u].end(), [&](int r, int l){
                if(seg_id[r] == -1) return false;
                if(seg_id[l] == -1) return true;
                return seg_tree[seg_id[r]].t.size() > seg_tree[seg_id[l]].t.size();
            });
            if(seg_id[g[u][0]] == -1){
                if(q[u].first != -1) {
                    seg_id[u] = seg_tree.size();
                    seg_tree.push_back(free_seg_tree);
                    seg_tree[seg_id[u]].Set(q[u].first, q[u].second);
                }
                else continue;
            }
            else{
                seg_id[u] = seg_id[g[u][0]];
                map<int, int> mp;
                for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
                    for(auto x:seg_tree[seg_id[g[u][i]]].t)
                        mp[x.first] += x.second;
                for(auto it = mp.rbegin(); it != mp.rend(); it ++)
                    seg_tree[seg_id[u]].Set(it->first, it->second);
                // for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
                //     seg_tree[seg_id[u]].merge(seg_tree[seg_id[g[u][i]]]);
                
                if(q[u].first != -1)
                    seg_tree[seg_id[u]].Set(q[u].first, q[u].second);
            }
        }
        // cout << u + 1 << endl;
        // seg_tree[seg_id[u]].print();
    }
    cout << seg_tree[seg_id[0]].t.rbegin()->second;
    return 0;
}

Compilation message

magictree.cpp: In function 'int main()':
magictree.cpp:104:34: 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]
  104 |                 for(int i = 1; i < g[u].size() && seg_id[g[u][i]] != -1; i ++)
      |                                ~~^~~~~~~~~~~~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 46 ms 11832 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 46 ms 8148 KB Output is correct
5 Correct 84 ms 12000 KB Output is correct
6 Correct 57 ms 8160 KB Output is correct

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 84 ms 15536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -