Submission #617793

#	Time	Username	Problem	Language	Result	Execution time	Memory
617793		vitkute	Untitled (POI11_dyn)	C++17	0 / 100	311 ms	29356 KiB

Main

#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define PB push_back
#define ALL(i_) i_.begin(), i_.end()
#define LOG2(x) (31 - __builtin_clz(x))
#define getBit(x, i) ((x >> i) & 1)
#define rd(l, r) (l + rng() % (r - l + 1))

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;

template<class X, class Y> bool minimize(X &x, const Y &y){
    X eps = 1e-9;
    if (x > y + eps) {
        x = y;
        return 1;
    }
    return 0;
}

template<class X, class Y> bool maximize(X &x, const Y &y) {
    X eps = 1e-9;
    if (x + eps < y) {
        x = y;
        return 1;
    }
    return 0;
}

template<class T> T Abs(const T &x) { return (x < 0 ? -x : x); }

const int mod = (int) 1e9 + 7;
const int oo = (int) 1e9 + 99;
const int maxn = (int) 3e5 + 11;
const int LOG = (int) 20;

int n, m;
int a[maxn], dp[maxn];
vector<int> adj[maxn];
ii s[maxn];

void DFS(int u = 1, int par = -1){
    s[u] = {a[u], u};
    if(par != -1) s[u].first += a[par];
    for(int v : adj[u]) if(v != par){
        s[u].first += a[v];
        DFS(v, u);
    }
}

bool comp(const ii &x, const ii &y){
    return (x.first > y.first || (x.first == y.first && a[x.second] > a[y.second]));
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #define TASK ""
    if(fopen(TASK".inp", "r")) {
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i < n; i++){
        int u, v; cin >> u >> v;
        adj[u].PB(v);
        adj[v].PB(u);
    }
    DFS();
    sort(s + 1, s + n + 1, comp);
    memset(dp, -1, sizeof dp);
    queue<int> que;
    for(int i = 1; i <= m; i++){
        que.push(s[i].second);
        dp[s[i].second] = 0;
    }
    while(!que.empty()){
        int u = que.front(); que.pop();
        for(int v : adj[u]){
            if(dp[v] == -1){
                dp[v] = dp[u] + 1;
                que.push(v);
            }
        }
    }
    int res = 0;
    for(int i = 1; i <= n; i++) if(a[i]) maximize(res, dp[i]);
    cout << res;
    return 0;
}

Compilation message (stderr)

dyn.cpp: In function 'int main()':
dyn.cpp:62:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dyn.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10