Submission #514859

#TimeUsernameProblemLanguageResultExecution timeMemory
514859angelo_torresConstruction of Highway (JOI18_construction)C++17
7 / 100
2077 ms19324 KiB
#include <bits/stdc++.h> #define f(i,j,n) for(int i = j; i < n; ++i) #define fr(i,j,n) for(int i = j; i >= n; --i) #define sz(v) (int) v.size() #define ff first #define ss second #define endl "\n" using namespace std; typedef vector<int> vi; typedef pair<int,int> ii; typedef vector<ii> vii; typedef long long ll; typedef pair<ll,ll> pll; typedef vector<ll> vll; typedef vector<pll> vpll; const int N = 1e4 + 20; const int M = 35; const ll inf = 1e16; int n,c[N]; vi adj[N],path[N]; void dfs(int v,int f){ for(auto u : adj[v]){ if(u == f) continue; path[u] = path[v]; path[u].push_back(u); dfs(u,v); } } void solve(){ cin >> n; f(i,1,n+1) cin >> c[i]; path[1] = {1}; dfs(1,0); f(i,1,n){ int a,b; cin >> a >> b; int ans = 0; f(j,0,sz(path[a])){ f(k,j+1,sz(path[a])){ if(c[path[a][j]] > c[path[a][k]]) ans++; } } for(auto u : path[a]) c[u] = c[b]; adj[a].push_back(b); adj[b].push_back(a); cout << ans << endl; f(j,2,n+1) path[j].clear(); dfs(1,0); } } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int tc = 1; // cin >> tc; f(i,1,tc+1){ // cout << "Case #" << i << ": "; solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...