제출 #400015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
400015		syl123456	Hard route (IZhO17_road)	C++17	0 / 100	1 ms	204 KiB

road

#include <bits/stdc++.h>
#define all(i) (i).begin(), (i).end()
#define debug(x) cerr << "Line(" << __LINE__ << ") -> " << #x << " is " << x << endl
using namespace std;
template<typename T1, typename T2>
ostream& operator << (ostream &i, pair<T1, T2> j) {
    return i << j.first << ' ' << j.second;
}
template<typename T>
ostream& operator << (ostream &i, vector<T> j) {
    i << '{' << j.size() << ':';
    for (T ii : j) i << ' ' << ii;
    return i << '}';
}
typedef long long ll;
typedef pair<int, int> pi;
vector<vector<int>> g;
vector<vector<pi>> v;
vector<pi> tot;
pi dfs(int i, int p) {
    if (g[i].size() == 1) v[i].emplace_back(0, 1);
    for (int j : g[i]) if (j != p) {
        pi tmp = dfs(j, i);
        ++tmp.first;
        v[i].push_back(tmp);
        if (tmp.first > tot[i].first) tot[i] = tmp;
        else if (tmp.first == tot[i].first) tot[i].second += tmp.second;
    }
    return tot[i];
}
pair<ll, ll> ans;
void upd(int i) {
    sort(all(v[i]), [](pi i, pi j){return i.first > j.first;});
    if (v[i].size() < 3) return;
    ll tmp = v[i][0].first * ll(v[i][1].first + v[i][2].first);
    if (tmp < ans.first) return;
    if (tmp > ans.first) ans = make_pair(tmp, 0);
    ll dp[3]{};
    for (int j = 0; j < v[i].size() && v[i][j].first >= v[i][2].first; ++j) {
        if (v[i][j].first == v[i][2].first)
            dp[2] += dp[1] * v[i][j].second;
        if (v[i][j].first == v[i][1].first)
            dp[1] += dp[0] * v[i][j].second;
        if (v[i][j].first == v[i][0].first)
            dp[0] += v[i][j].second;
    }
    if (v[i][2].first == v[i][0].first) ans.second += dp[1];
    else if (v[i][1].first == v[i][0].first) ans.second += 2 * dp[2];
    else ans.second += dp[2];
}
void dfs2(int i, int p) {
    if (~p) {
        pi tmp = tot[p];
        if (tmp.first == tot[i].first + 1) tmp.second -= tot[i].second;
        if (tmp.second == 0) {
            if (v[p].size() == 1) goto f1;
            tmp = v[p][1];
            for (int j = 2; j < v[p].size() && v[p][j].first == tmp.first; ++j)
                tmp.second += v[p][j].second;
        }
        ++tmp.first;
        v[i].push_back(tmp);
        if (tmp.first > tot[i].first) tot[i] = tmp;
        else if (tmp.first == tot[i].first) tot[i].second += tmp.second;
    }
    f1:
    upd(i);
    for (int j : g[i]) if (j != p) dfs2(j, i);
}
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    g.resize(n), v.resize(n), tot.assign(n, pi(0, 1));
    for (int i = 0; i < n - 1; ++i) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        g[x].push_back(y), g[y].push_back(x);
    }
    dfs(0, -1);
    dfs2(0, -1);
    if (ans.first) cout << ans;
    else cout << "0 1";
}

컴파일 시 표준 에러 (stderr) 메시지

road.cpp: In function 'void upd(int)':
road.cpp:39: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]
   39 |     for (int j = 0; j < v[i].size() && v[i][j].first >= v[i][2].first; ++j) {
      |                     ~~^~~~~~~~~~~~~
road.cpp: In function 'void dfs2(int, int)':
road.cpp:58:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |             for (int j = 2; j < v[p].size() && v[p][j].first == tmp.first; ++j)
      |                             ~~^~~~~~~~~~~~~

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