记录编号	575216	评测结果	WWWWWWWWWW
题目名称	van玩galgame	最终得分	0
用户昵称	Tab↹	是否通过	未通过
代码语言	C++	运行时间	3.059 s
提交时间	2022-09-07 20:23:48	内存使用	20.32 MiB

/*
* @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[i->first->num])
            cur = mval[i->first->num];
        if(cur > mval[begin]) {
            mval[begin] = cur;
            arr[begin].max_next = i->first->num;
        }
    }
}

void search_ans() {
    int res = INT_MIN;
    for(int i = 0; i < n; ++i) {
        if(reached[i]) {
            for(auto j = arr[i].next.begin(); j != arr[i].next.end(); ++j) {
                if(j->first->num != arr[i].max_next) {
                    int tmp = j->second + mval[j->first->num];
                    if(tmp > res)
                        res = tmp;
                }
            }
        }
    }
    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];
    search_ans();
    fout << ans;
    
    delete []reached;
    delete []mval;
    delete []arr;
    return 0;
}