제출 #385922

#제출 시각아이디문제언어결과실행 시간메모리
385922alireza_kaviani친구 (IOI14_friend)C++11
35 / 100
4 ms2816 KiB
#include <bits/stdc++.h> #include "friend.h" using namespace std; typedef pair<int, int> pii; #define X first #define Y second #define all(x) (x).begin() , (x).end() #define SZ(x) int(x.size()) const int MAXN = 1e5 + 10; const int MOD = 1e9 + 7; int par[MAXN] , sz[MAXN] , val[MAXN] , dp[2][MAXN] , mark[MAXN]; vector<int> adj[MAXN]; vector<pii> E; int Find(int v){ return (par[v] == -1 ? v : par[v] = Find(par[v])); } void Union(int v , int u , int flag){ v = Find(v); u = Find(u); if(v == u) return; if(sz[v] < sz[u]) swap(v , u); par[u] = v; sz[v] += sz[u]; if(flag == 0) val[v] += val[u]; if(flag == 1) val[v] = max(val[v] , val[u]); } void DFS(int v , int p = -1){ mark[v] = 1; dp[1][v] = val[v]; for(int u : adj[v]){ if(u == p) continue; DFS(u , v); dp[0][v] += max(dp[0][u] , dp[1][u]); dp[1][v] += dp[0][u]; } } int findSample(int n,int confidence[],int host[],int protocol[]){ for(int i = 0 ; i < n ; i++){ val[i] = confidence[i]; par[i] = -1; sz[i] = 1; } for(int i = 1 ; i < n ; i++){ if(protocol[i] == 0){ E.push_back({i , host[i]}); } else{ Union(i , host[i] , (protocol[i] == 2)); } } for(pii i : E){ adj[Find(i.X)].push_back(Find(i.Y)); adj[Find(i.Y)].push_back(Find(i.X)); } int ans = 0; for(int i = 1 ; i <= n ; i++){ if(i == Find(i) && !mark[i]){ DFS(i); ans += max(dp[0][i] , dp[1][i]); } } return ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...