Submission #242327

#TimeUsernameProblemLanguageResultExecution timeMemory
242327dwscMagic Tree (CEOI19_magictree)C++14
37 / 100
301 ms430056 KiB
#include <bits/stdc++.h> #define int long long using namespace std; typedef pair<int,int> ii; int n,m,k; vector<int> adj[100010]; int ripe[100010]; int weight[100010]; int memo[100010][1010]; int dp(int u,int j){ if (j == 0) return 0; if (memo[u][j] != -1) return memo[u][j]; int s = 0; for (int i = 0; i < adj[u].size(); i++){ int v = adj[u][i]; s += dp(v,j); } if (j == ripe[u]) s += weight[u]; if (weight[u] != 0)return memo[u][j] = max(s,dp(u,j-1)); else return memo[u][j] = s; } struct node{ int s,e,m,v; node *l,*r; node (int _s,int _e){ s = _s; e = _e; m = (s+e)/2; v = 0; if (s != e){ l = new node(s,m); r = new node(m+1,e); } } void up(int x,int v1){ if (s == e) {v = v1;return;} if (x <= m) l->up(x,v1); else r->up(x,v1); v = max(l->v,r->v); } int rmq(int x,int y){ if (s == x && e == y) return v; if (y <= m) return l->rmq(x,y); if (x > m) return r->rmq(x,y); return max(l->rmq(x,m),r->rmq(m+1,y)); } }*root; main(){ ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> k; int isline = 1; for (int i = 2; i <= n; i++){ int p; cin >> p; if (i-1 != p) isline = 0; adj[p].push_back(i); } vector<int> temp; temp.push_back(0); for (int i = 0; i < m; i++){ int v,d,w; cin >> v >> d >> w; ripe[v] = d; weight[v] = w; temp.push_back(d); } sort(temp.begin(),temp.end()); temp.erase(unique(temp.begin(),temp.end()),temp.end()); for (int i = 1; i <= n; i++) ripe[i] = lower_bound(temp.begin(),temp.end(),ripe[i])-temp.begin(); //for (int i = 1; i <= n; i++) cout << ripe[i] << "\n"; if (k <= 20){ for (int i = 1; i<= n; i++){ for (int j = 0; j < temp.size(); j++){ memo[i][j] = -1; } } cout << dp(1,temp.size()-1); } else if (isline){ vector<ii> v; int ans = 0; root = new node(0,temp.size()-1); for (int i = 1; i <= n; i++){ int q = root->rmq(0,ripe[i]); ans = max(ans,q+1); root->up(ripe[i],q+1); } cout << ans; } else{ int ans = 0; for (int i = 1; i <= n; i++) ans += weight[i]; cout << ans; } }

Compilation message (stderr)

magictree.cpp: In function 'long long int dp(long long int, long long int)':
magictree.cpp:14:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < adj[u].size(); i++){
                     ~~^~~~~~~~~~~~~~~
magictree.cpp: At global scope:
magictree.cpp:48:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
magictree.cpp: In function 'int main()':
magictree.cpp:74:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int j = 0; j < temp.size(); j++){
                         ~~^~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...