Submission #312226

#	Time	Username	Problem	Language	Result	Execution time	Memory
312226		joseacaz	Traffic (IOI10_traffic)	C++17	0 / 100	16 ms	23808 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 = -1)
{
    sum += node;
    down[node] = node;
    for(auto i : Graph[node])
        if(i != p)
        {
            dfs(i, node);
            down[node] += down[i];
            maxim[node] = max(maxim[node], down[i]);
        }
}

int LocateCentre(int N, int P[], int S[], int D[])
{
    for(int i = 0; i < N - 1; i++)
        Graph[S[i]].pb(D[i]);
    
    dfs(0);
    int ans = 0;
    ll minim = (1LL << 60LL);
    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;
}


/*
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;
}
*/

/*
- 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...);
      |  ^~~

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