oj.uz

Submission #673774

# Submission time Handle Problem Language Result Execution time Memory
673774 2022-12-22T02:19:38 Z Cookie Traffic (IOI10_traffic) C++14
0 / 100
 1 ms 1492 KB 
#include<bits/stdc++.h>
 
using namespace std;
 #include "traffic.h"
 
 
 
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
typedef unsigned long long ull;
#include<fstream>
ifstream fin("ss.inp");
ofstream fout("ss.out");
#define pii pair<int, int>
#define pll pair<ll, ll>
 
const ll mod = 1e9 + 7, mod2 = 1e9 + 9;
const int mxn = 5e4, mxq = 1e5, sq = 800, mxm = 1e5;
int n;
vt<int>adj[mxn + 1];
ll sm[mxn + 1], a[mxn + 1], all = 0, s[mxn + 1], d[mxn + 1];
ll ans = 1e16, id = -1;
void dfs(int s, int pre){
    sm[s] = a[s];
    ll mx = 0;
    for(auto i: adj[s]){
        if(i != pre){
            dfs(i, s);
        sm[s] += sm[i]; mx = max(mx, sm[i]);
        }
    }
    mx = max(mx, all - sm[s]);
    
    if(mx < ans){
        ans = mx; id = s;
    }
}
int LocateCentre(int n, int a[], int s[], int d[]) {
   
    for(int i = 0; i < n; i++){
        all += 1LL * a[i]; 
    }
    forr(i, 0, n - 1){
        
        adj[s[i]].pb(d[i]); adj[d[i]].pb(s[i]);
    }
    dfs(0, -1);
    return(id);
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Incorrect 1 ms 1492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Incorrect 1 ms 1492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Incorrect 1 ms 1492 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Incorrect 1 ms 1492 KB Output isn't correct
3 Halted 0 ms 0 KB -