Submission #312229

#	Time	Username	Problem	Language	Result	Execution time	Memory
312229		joseacaz	Traffic (IOI10_traffic)	C++17	100 / 100	1266 ms	161016 KiB

traffic

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define fst first
#define snd second
 
int pct(int x) { return __builtin_popcount(x); }
 
// TO_STRING, credits: Benq
#define ts to_string
string ts(char c) { return string(1,c); }
string ts(bool b) { return b ? "true" : "false"; }
string ts(const char* s) { return (string)s; }
string ts(string s) { return s; }
template<class A> string ts(complex<A> c) { 
	stringstream ss; ss << c; return ss.str(); }
string ts(vector<bool> v) { 
	string res = "{"; for(int i = 0; i < sz(v); i++) res += char('0'+v[i]);
	res += "}"; return res; }
template<size_t SZ> string ts(bitset<SZ> b) {
	string res = ""; for(int i = 0; i < SZ; i++) res += char('0'+b[i]);
	return res; }
template<class A, class B> string ts(pair<A,B> p);
template<class T> string ts(T v) { // containers with begin(), end()
	bool fst = 1; string res = "{";
	for (const auto& x: v) {
		if (!fst) res += ", ";
		fst = 0; res += ts(x);
	}
	res += "}"; return res;
}
template<class A, class B> string ts(pair<A,B> p) {
	return "("+ts(p.first)+", "+ts(p.second)+")"; }
    
// DEBUG, credits: Benq
void DBG() {
    cerr << "]" << endl;
}
template<class H, class... T> void DBG(H h, T... t) {
	cerr << ts(h);
    if (sizeof...(t))
        cerr << ", ";
	DBG(t...);
}
 
#ifdef LOCAL // compile with -DLOCAL
#define dbg(...) cerr << "LINE(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#define optimizeIO() 0
#define openFiles() 0
#else
#define dbg(...) 0
#define optimizeIO() ios_base::sync_with_stdio(0); cin.tie(0)
#define openFiles() freopen("file.in", "r", stdin); freopen("file.out", "w", stdout)
#endif
 
const int MAXN = 1000005;
ll sum = 0, down[MAXN], maxim[MAXN];
vi Graph[MAXN];
 
void dfs(int node, int P[], int p = -1)
{
    sum += P[node];
    down[node] = P[node];
    for(auto i : Graph[node])
        if(i != p)
        {
            dfs(i, P, node);
            down[node] += down[i];
            maxim[node] = max(maxim[node], down[i]);
        }
}
 
int LocateCentre(int N, int P[], int S[], int D[])
{
    sum = 0;
    for(int i = 0; i < N; i++)
    {
        Graph[i].clear();
        down[i] = 0;
        maxim[i] = 0;
    }

    for(int i = 0; i < N - 1; i++)
    {
        Graph[S[i]].pb(D[i]);
        Graph[D[i]].pb(S[i]);
    }
    
    dfs(0, P);
    for(int i = 0; i < N; i++)
        dbg(down[i], maxim[i]);
    int ans = 0, minim = (1 << 30);
    for(int i = 0; i < N; i++)
        if(max(maxim[i], sum - down[i]) < minim)
        {
            minim = max(maxim[i], sum - down[i]);
            ans = i;
        }
    
    return ans;
}
 
 
#ifdef LOCAL
int main ()
{
    optimizeIO();
    int n;
    cin >> n;
    int p[n];
    for(int i = 0; i < n; i++)
        cin >> p[i];
    int u[n - 1], v[n - 1];
    for(int i = 0; i < n - 1; i++)
        cin >> u[i] >> v[i];
    cout << LocateCentre(n, p, u, v) << "\n";
    return 0;
}
#endif
 
/*
- if use ceil/floor, cast to int.
*/

Compilation message (stderr)

traffic.cpp: In function 'void DBG(H, T ...)':
traffic.cpp:54:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   54 |     if (sizeof...(t))
      |     ^~
traffic.cpp:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   56 |  DBG(t...);
      |  ^~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:64:18: warning: statement has no effect [-Wunused-value]
   64 | #define dbg(...) 0
      |                  ^
traffic.cpp:104:9: note: in expansion of macro 'dbg'
  104 |         dbg(down[i], maxim[i]);
      |         ^~~

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25