Submission #1589025
Source Code Expand
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define REP(i, n) rep(i, 0, n)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define int long long
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;
int n, k;
vector<int> G[51];
int d[51];
int MAX = 0;
void dfs(int now, int pre, int sum, vector<bool> f){
f[now] = true;
chmax(MAX, sum);
rep(i, 0, G[now].size()){
int next = G[now][i];
if(next == pre || f[next]) continue;
chmax(MAX, sum + d[next]);
dfs(next, now, sum + d[next], f);
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
rep(i, 0, n) cin >> d[i];
rep(i, 0, k){
int x, y;
cin >> x >> y;
x--; y--;
G[x]. push_back(y);
G[y]. push_back(x);
}
rep(i, 0, n){
vector<bool> g(n, false);
dfs(i, -1, d[i], g);
}
cout << MAX << endl;
}
Submission Info
Submission Time |
|
Task |
C - お金の街 (The Money Town) |
User |
treeone |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
1125 Byte |
Status |
AC |
Exec Time |
75 ms |
Memory |
256 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
50 / 50 |
50 / 50 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample1.txt, sample2.txt, sample3.txt |
Subtask1 |
sample1.txt, sample2.txt, sample3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt |
Subtask2 |
sample1.txt, sample2.txt, sample3.txt, sub1_1.txt, sub1_2.txt, sub1_3.txt, sub1_4.txt, sub2_1.txt, sub2_2.txt, sub2_3.txt, sub2_4.txt, sub2_5.txt, sub2_6.txt |
Case Name |
Status |
Exec Time |
Memory |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |
sub1_1.txt |
AC |
1 ms |
256 KB |
sub1_2.txt |
AC |
1 ms |
256 KB |
sub1_3.txt |
AC |
1 ms |
256 KB |
sub1_4.txt |
AC |
1 ms |
256 KB |
sub2_1.txt |
AC |
1 ms |
256 KB |
sub2_2.txt |
AC |
6 ms |
256 KB |
sub2_3.txt |
AC |
6 ms |
256 KB |
sub2_4.txt |
AC |
16 ms |
256 KB |
sub2_5.txt |
AC |
33 ms |
256 KB |
sub2_6.txt |
AC |
75 ms |
256 KB |