比赛 EYOI与SBOI开学欢乐赛3rd 评测结果 WWWWWWWWWW
题目名称 van玩galgame 最终得分 0
用户昵称 Tab↹ 运行时间 2.782 s
代码语言 C++ 内存使用 20.32 MiB
提交时间 2022-09-05 21:22:04
显示代码纯文本
/*
* @brief USELESS code, WRONG answer
**/
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <algorithm>
#include <bits/stl_pair.h>

using namespace std;

using ll = long long;

class Node {
public:
    int num;
    vector<pair<Node*, ll>> next; 
    int max_next;   
    Node* last;
};

int n;
ll ans;
Node* arr;
ll* mval;
bool* reached;

void search_mval(int begin = 0) {
    if(arr[begin].next.empty()) {
        mval[begin] = 0;
        arr[begin].max_next = -1;
        return;
    }
    mval[begin] = LLONG_MIN;
    ll cur;
    for(auto i = arr[begin].next.begin(); i != arr[begin].next.end(); ++i) {
        search_mval(i->first->num);
        cur = mval[i->first->num] + i->second;
        if(cur > mval[begin]) {
            mval[begin] = cur;
            arr[begin].max_next = i->first->num;
        }
    }
}

void search_ans(int begin = 0, int end = -1) {
    if(arr[begin].next.empty()) {
        return;
    }
    ll res = mval[0];
    for(int i = 0; i != -1; i = arr[i].max_next) {
        for(auto j = arr[i].next.begin(); j != arr[i].next.end(); ++j) {
            if(j->first->num != arr[i].max_next) {
                if(j->second + mval[j->first->num] > res) {
                    res = j->second + mval[j->first->num];
                } 
            }  
        }
    }
    ans = res;
}

int main(void) {
    ifstream fin("galgame.in");
    ofstream fout("galgame.out");
    fin >> n;
    arr = new Node[n];
    mval = new ll[n];
    reached = new bool[n];

    for(int k, i = 0; i < n; ++i) {
        arr[i].num = i;
        fin >> k;
        if(k != 0) {
            ll val;
            int next;
            for(int j = 0; j < k; ++j) {
                fin >> val >> next;
                arr[i].next.push_back({arr+next-1, val});
            }
        }
    }

    search_mval();
    for(int i = arr[0].max_next; i != -1; i = arr[i].max_next)
        reached[i] = true;
    ans = mval[0];
    fout << ans;
    
    delete []reached;
    delete []mval;
    delete []arr;
    return 0;
}