# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
304591 | 2020-09-21T14:48:58 Z | rocks03 | Islands (IOI08_islands) | C++14 | 18 ms | 23968 KB |
#include<bits/stdc++.h> using namespace std; #define ll long long #define pld pair<long double, int> #define pii pair<int, int> #define pll pair<ll, ll> #define pb push_back #define ff first #define ss second #define SZ(x) ((int)(x).size()) #define ld long double mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MAXN = 1e6+100; int N; vector<pii> adj[MAXN]; void read(){ cin >> N; for(int i = 0; i < N; i++){ int u, w; cin >> u >> w; --u; adj[i].pb({u, w}); adj[u].pb({i, w}); } } bool vis[MAXN], vis2[MAXN]; vector<int> componente; void dfs(int v){ vis[v] = true; componente.pb(v); for(auto u : adj[v]){ if(!vis[u.ff]){ dfs(u.ff); } } } ll dfs2(int v){ ll ans = 0; vis2[v] = true; for(auto u : adj[v]){ if(!vis2[u.ff]){ ans = max(ans, dfs2(u.ff) + u.ss); } } vis2[v] = false; return ans; } void solve(){ read(); ll ans = 0; for(int i = 0; i < N; i++){ if(!vis[i]){ dfs(i); ll res = 0; for(auto v : componente){ res = max(res, dfs2(v)); } ans += res; componente.clear(); } } cout << ans; } int main(){ freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
2 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
3 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
4 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
5 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
6 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
7 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
8 | Incorrect | 18 ms | 23936 KB | Output isn't correct |
9 | Incorrect | 18 ms | 23936 KB | Output isn't correct |
10 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
11 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 18 ms | 23936 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 18 ms | 23968 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 17 ms | 23936 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |