Submission #859811

#	Time	Username	Problem	Language	Result	Execution time	Memory
859811		aykhn	Traffic (IOI10_traffic)	C++14	0 / 100	101 ms	75264 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

// author: aykhn

using namespace std;

typedef long long ll;

#define TC int t; cin >> t; while (t--) _();
#define OPT ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define mpr make_pair
#define eb emplace_back
#define pb push_back
#define ts to_string
#define fi first
#define se second
#define ins insert
#define inf 0x3F3F3F3F
#define infll 0x3F3F3F3F3F3F3F3FLL
#define bpc __builtin_popcount

const int MXN = 1e6 + 5;

int n, sz = 1;
vector<int> st;
vector<pii> adj[MXN];
int used[MXN];
int dist[MXN];
int in[MXN];
int out[MXN];
int tim = -1;
pii mx[MXN];
int ans[MXN];

void make(int lx, int rx, int val, int l, int r, int x)
{
    if (l >= rx || r <= lx) return;
    if (l >= lx && r <= rx)
    {
        st[x] = max(st[x], val);
        return;
    }
    int mid = (l + r) >> 1;
    make(lx, rx, val, l, mid, 2*x + 1);
    make(lx, rx, val, mid, r, 2*x + 2);
}

int get(int ind, int l, int r, int x)
{
    if (l + 1 == r) return st[x];
    int mid = (l + r) >> 1;
    if (ind < mid) return max(st[x], get(ind, l, mid, 2*x + 1));
    else return max(st[x], get(ind, mid, r, 2*x + 2));
}

void dfs(int a, int w)
{
    in[a] = ++tim;
    dist[a] = w;
    used[a] = 1;
    for (int i = 0; i < adj[a].size(); i++)
    {
        pii v = adj[a][i];
        if (used[v.fi]) continue;
        dfs(v.fi, w + v.se);

        if (mx[v.fi].fi + v.se > mx[a].fi)
        {
            mx[a].se = mx[a].fi;
            mx[a].fi = mx[v.fi].fi + v.se;
        }
        else
        {
            mx[a].se = max(mx[a].se, mx[v.fi].fi + v.se);
        }
    }
    out[a] = tim;
}

void dfs1(int a)
{
    used[a] = 1;

    for (int i = 0; i < adj[a].size(); i++)
    {
        pii v = adj[a][i];
        if (used[v.fi]) continue;
        dfs1(v.fi);

        if (mx[a].fi == mx[v.fi].fi + v.se) make(in[v.fi], out[v.fi] + 1, mx[a].se - dist[a], 0, sz, 0);
        else make(in[v.fi], out[v.fi] + 1, mx[a].fi - dist[a], 0, sz, 0);
    }
}

void dfs2(int a, int w)
{
    used[a] = 1;
    ans[a] = max({dist[a], w, mx[a].fi});
    for (int i = 0; i < adj[a].size(); i++)
    {
        pii v = adj[a][i];
        if (used[v.fi]) continue;

        if (mx[a].fi == mx[v.fi].fi + v.se)
        {
            dfs2(v.fi, max(w, mx[a].se) + v.se);
        }
        else
        {
            dfs2(v.fi, max(w, mx[a].fi) + v.se);
        }

    }
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
	n = N;
	while (sz < n) sz <<= 1;
    st.assign(sz << 1, 0);
	for (int i = 1; i < n; i++)
    {
		int u = S[i];
		int v = D[i];
        adj[u].pb(mpr(v, pp[v]));
        adj[v].pb(mpr(u, pp[u]));
    }
    dfs(0, 0);
    for (int i = 1; i <= n; i++) used[i] = 0;
    dfs1(0);
    for (int i = 1; i <= n; i++) used[i] = 0;
    dfs2(0, 0);
	for (int i = 0; i < n; i++)
	{
		adj[S[i]].pb(mpr(D[i], pp[D[i]]));
		adj[D[i]].pb(mpr(S[i], pp[S[i]]));
	}
	int mni = 0;
	int mn = inf;
	for (int i = 0; i < n; i++)
    {
		int x = max({ans[i] + pp[i], pp[i] + mx[i].fi - dist[i], dist[i] + get(in[i], 0, sz, 0)});
		if (x < mn)
		{
			mni = i;
			mn = x;
		}
    }
}

Compilation message (stderr)

traffic.cpp: In function 'void dfs(int, int)':
traffic.cpp:64:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
traffic.cpp: In function 'void dfs1(int)':
traffic.cpp:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
traffic.cpp: In function 'void dfs2(int, int)':
traffic.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 0; i < adj[a].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:140:6: warning: variable 'mni' set but not used [-Wunused-but-set-variable]
  140 |  int mni = 0;
      |      ^~~
traffic.cpp:151:1: warning: no return statement in function returning non-void [-Wreturn-type]
  151 | }
      | ^

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