Submission #1589131
Source Code Expand
#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, K; vector<ll> d; vector<int> x, y; int G[50][50] = {}; ll dfs(int t, ll sum, vector<bool> used) { used[t] = true; ll res = 0; bool ng = true; for (int i = 0; i < n; i++) { if (!G[t][i] || (used[i])) continue; res = max(res, dfs(i, sum + d[t], used)); ng = false; } if (ng) return sum + d[t]; return res; } int main(void) { cin >> n >> K; d.resize(n); x.resize(K); y.resize(K); for (int i = 0; i < n; i++) { cin >> d[i]; } for (int i = 0; i < K; i++) { cin >> x[i] >> y[i]; x[i]--, y[i]--; G[x[i]][y[i]] = G[y[i]][x[i]] = 1; } ll ans = 0; for (int i = 0; i < n; i++) { vector<bool> used(n, false); ans = max(ans, dfs(i, 0, used)); } cout << ans << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | C - お金の街 (The Money Town) |
User | legosuke |
Language | C++14 (GCC 5.4.1) |
Score | 100 |
Code Size | 872 Byte |
Status | AC |
Exec Time | 101 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 | 7 ms | 256 KB |
sub2_3.txt | AC | 7 ms | 256 KB |
sub2_4.txt | AC | 22 ms | 256 KB |
sub2_5.txt | AC | 44 ms | 256 KB |
sub2_6.txt | AC | 101 ms | 256 KB |