# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
217471 | 2020-03-29T20:12:27 Z | tatyam | Islands (IOI08_islands) | C++17 | 469 ms | 131076 KB |
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<ll, ll>; const ll INF = 0x1fffffffffffffff; #define name3(a,b,c,d,...) d #define rep1(a) for(ll i = 0; i < a; i++) #define rep3(i,a,b) for(ll i = a; i < b; i++) #define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__) #define rrep(a) for(ll i = a; i--; ) #define each(i,a) for(auto&& i : a) #define all(a) begin(a), end(a) template<class T, class U> bool chmin(T& a, const U& b){ if(a > b){ a = b; return 1; } return 0; } template<class T, class U> bool chmax(T& a, const U& b){ if(a < b){ a = b; return 1; } return 0; } vector<bool> used; vector<vector<pll>> g; vector<ll> in; ll ans = 0; void solve(ll start){ if(used[start]) return; vector<ll> list = {start}; used[start] = 1; rep(list.size()){ ll at = list[i]; each(i, g[at]) if(!used[i.first]){ used[i.first] = 1; list.push_back(i.first); } } ll mx = 0; ll dex = -1; unordered_map<ll, ll> dp; each(i, list) if(g[i].size() == 1){ ll cnt = 0; ll at = i; while(g[at].size() < 3){ cnt += g[at][0].second; at = g[at][0].first; } chmax(dp[at], cnt); if(chmax(mx, cnt)) dex = at; } if(!mx){ ll min = INF; each(at, list){ ans += g[at][0].second; chmin(min, g[at][0].second); } ans -= min; return; } vector<ll> circle, dist; ll at = dex; do{ circle.push_back(at); dist.push_back(g[at][0].second); at = g[at][0].first; } while(at != dex); circle.push_back(at); dp[dex] = 0; auto dp2 = dp; rep(i, 1, dist.size()) chmax(dp[circle[i + 1]], dp[circle[i]] + dist[i]); rrep(dist.size() - 1) chmax(dp2[circle[i]], dp2[circle[i + 1]] + dist[i]); ans += mx + max(dp[dex], dp2[dex]); } int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); ll n; cin >> n; used.resize(n); g.resize(n); in.resize(n); rep(n){ ll a, b; cin >> a >> b; a--; g[i].emplace_back(a, b); } rep(n) g[g[i][0].first].emplace_back(i, g[i][0].second); rep(n) solve(i); cout << ans << endl; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 384 KB | Output is correct |
2 | Runtime error | 212 ms | 131076 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Incorrect | 4 ms | 384 KB | Output isn't correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
7 | Correct | 5 ms | 384 KB | Output is correct |
8 | Runtime error | 198 ms | 131076 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
9 | Correct | 5 ms | 384 KB | Output is correct |
10 | Incorrect | 5 ms | 384 KB | Output isn't correct |
11 | Correct | 5 ms | 256 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 5 ms | 512 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 211 ms | 131076 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 14 ms | 2176 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 33 ms | 7540 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 131 ms | 25172 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Runtime error | 319 ms | 131076 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 404 ms | 110460 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 458 ms | 102824 KB | Output is correct |
2 | Runtime error | 469 ms | 131076 KB | Execution killed with signal 9 (could be triggered by violating memory limits) |
3 | Halted | 0 ms | 0 KB | - |