Submission #947568

#	Time	Username	Problem	Language	Result	Execution time	Memory
947568		Pring	Hard route (IZhO17_road)	C++17	100 / 100	527 ms	92344 KiB

road

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

#define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 500005;
int n;
vector<int> edge[MXN];
pii d[MXN], u[MXN];
int pnt[MXN];

pii operator+(pii a, pii b) {
    if (a < b) swap(a, b);
    if (a.fs == b.fs) a.sc += b.sc;
    return a;
}

int SUM(vector<int> &v) {
    int ans = 0;
    for (auto &i : v) ans += i;
    return ans;
}

struct P {
    pii a, b;
    void init() {
        a = mp(0LL, 0LL);
        b = mp(0LL, 0LL);
    }
    void PUSH(pii x) {
        if (x.fs > a.fs) {
            b = a;
            a = x;
        } else if (x.fs == a.fs) {
            a.sc += x.sc;
        } else if (x.fs > b.fs) {
            b = x;
        } else if (x.fs == b.fs) {
            b.sc += x.sc;
        }
    }
    pii GET(pii x) {
        if (x.fs != a.fs) return a;
        if (x.sc == a.sc) return b;
        return mp(a.fs, a.sc - x.sc);
    }
} p[MXN];

bool chain() {
    int big = 0;
    FOR(i, 1, n + 1) big = max(big, (int) edge[i].size());
    return big <= 2;
}

void DFS1(int id, int par) {
    pnt[id] = par;
    d[id] = mp(0LL, 1LL);
    for (auto &i : edge[id]) {
        if (i == par) continue;
        DFS1(i, id);
        d[id] = d[id] + mp(d[i].fs + 1, d[i].sc);
    }
}

void DFS2(int id, int par) {
    u[id] = p[par].GET(mp(d[id].fs + 1, d[id].sc));
    u[id].fs++;
    p[id].init();
    p[id].PUSH(u[id]);
    for (auto &i : edge[id]) {
        if (i == par) continue;
        p[id].PUSH(mp(d[i].fs + 1, d[i].sc));
    }
    for (auto &i : edge[id]) {
        if (i == par) continue;
        DFS2(i, id);
    }
}

pii calc(int id) {
    if (edge[id].size() < 3) return mp(0LL, 0LL);
    vector<int> c(3, -1);
    vector<vector<int>> v(3);
    c[0] = u[id].fs;
    v[0].push_back(u[id].sc);
    for (auto &i : edge[id]) {
        if (i == pnt[id]) continue;
        debug(d[i].fs + 1, d[i].sc);
        bool f = false;
        FOR(j, 0, 3) if (d[i].fs + 1 == c[j]) {
            v[j].push_back(d[i].sc);
            f = true;
            break;
        }
        if (f) continue;
        FOR(j, 0, 3) if (d[i].fs + 1 > c[j]) {
            c.insert(c.begin() + j, d[i].fs + 1);
            v.insert(v.begin() + j, vector<int>(1, d[i].sc));
            break;
        }
        if (c.size() == 4) {
            c.pop_back();
            v.pop_back();
        }
    }
    if (v[0].size() >= 3) {
        int x = 2 * c[0] * c[0];
        int s = SUM(v[0]), y = 0;
        for (auto &i : v[0]) y += i * (s - i);
        return mp(x, y / 2);
    }
    if (v[0].size() == 2) {
        int x = c[0] * (c[0] + c[1]);
        return mp(x, (v[0][0] + v[0][1]) * SUM(v[1]));
    }
    if (v[1].size() >= 2) {
        int x = 2 * c[0] * c[1];
        int s = SUM(v[1]), y = 0;
        for (auto &i : v[1]) y += i * (s - i);
        return mp(x, y / 2);
    }
    return mp(c[0] * (c[1] + c[2]), v[1][0] * SUM(v[2]));
}

void miku() {
    int x, y;
    cin >> n;
    FOR(i, 1, n) {
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    if (chain()) {
        cout << "0 1" << '\n';
        return;
    }
    int rt = [&]() -> int {
        FOR(i, 1, n + 1) if (edge[i].size() == 1) return i;
        return 0;
    }();
    DFS1(rt, 0);
    p[rt].init();
    p[rt].PUSH(mp(0LL, 1LL));
    for (auto &i : edge[rt]) p[rt].PUSH(mp(d[i].fs + 1, d[i].sc));
    for (auto &i : edge[rt]) DFS2(i, rt);
    debug(rt);
    FOR(i, 1, n + 1) debug(i, u[i].fs, u[i].sc);
    pii ans = mp(0LL, 0LL);
    FOR(i, 1, n + 1) {
        // ans = ans + calc(i);
        pii x = calc(i);
        debug(i, x.fs, x.sc);
        ans = ans + x;
    }
    cout << ans.fs << ' ' << ans.sc << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    miku();
    return 0;
}

Compilation message (stderr)

road.cpp: In function 'pii calc(long long int)':
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
road.cpp:103:9: note: in expansion of macro 'debug'
  103 |         debug(d[i].fs + 1, d[i].sc);
      |         ^~~~~
road.cpp: In function 'void miku()':
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
road.cpp:161:5: note: in expansion of macro 'debug'
  161 |     debug(rt);
      |     ^~~~~
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
road.cpp:162:22: note: in expansion of macro 'debug'
  162 |     FOR(i, 1, n + 1) debug(i, u[i].fs, u[i].sc);
      |                      ^~~~~
road.cpp:11:20: warning: statement has no effect [-Wunused-value]
   11 | #define debug(...) 39
      |                    ^~
road.cpp:167:9: note: in expansion of macro 'debug'
  167 |         debug(i, x.fs, x.sc);
      |         ^~~~~

• Subtask 1: 19 / 19
• Subtask 2: 33 / 33
• Subtask 3: 48 / 48