比赛 |
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;
}