Submission #391387

#	Time	Username	Problem	Language	Result	Execution time	Memory
391387		Killer2501	Hard route (IZhO17_road)	C++14	0 / 100	26 ms	39500 KiB

road

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define task "cowpatibility"
#define pll pair<ll, ll>
#define pii pair<pll, ll>
#define fi first
#define se second

using namespace std;
const ll mod =  998244353;
const ll N = 5e5+5;
const int base = 400;
ll n, m, t, k, T, ans, tong, lab[N], a[N], b[N], d[N], in[N], out[N], lazy[N*4];
ll st[N*4];
vector<ll> adj[N], kq, val[N];

string s[N], ss;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}
void build(ll id, ll l, ll r)
{
    if(l == r)
    {
        st[id] = a[l];
        return;
    }
    ll mid = (l + r) / 2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    st[id] = max(st[id*2], st[id*2+1]);
}
void down(ll id)
{
    if(lazy[id] == 0)return;
    lazy[id*2] += lazy[id];
    lazy[id*2+1] += lazy[id];
    st[id*2] += lazy[id];
    st[id*2+1] += lazy[id];
    lazy[id] = 0;
}
void update(ll id, ll l, ll r, ll u, ll v, ll val)
{
    if(u <= l && r <= v)
    {
        st[id] += val;
        lazy[id] += val;
        return;
    }
    if(u > r || l > v || u > v)return;
    ll mid = (l + r) / 2;
    down(id);
    update(id*2, l, mid, u, v, val);
    update(id*2+1, mid+1, r, u, v, val);
    st[id] = max(st[id*2], st[id*2+1]);
}
ll get(ll id, ll l, ll r, ll u, ll v)
{
    if(u <= l && r <= v)return st[id];
    if(u > r || l > v || u > v)return -mod;
    ll mid = (l + r) / 2;
    down(id);
    return max(get(id*2, l, mid, u, v), get(id*2+1, mid+1, r, u, v));
}
void dfs1(ll u, ll p)
{
    in[u] = ++k;
    for(ll v : adj[u])
    {
        if(v == p)continue;
        b[v] = b[u] + 1;
        dfs1(v, u);
    }
    if(adj[u].size() == 1)a[in[u]] = b[u];
    else a[in[u]] = -mod;
    out[u] = k;

}
void dfs2(ll u, ll p)
{
    if(adj[u].size() > 1)
    {
        vector<ll> val;
        val.pb(max(get(1, 1, n, 1, in[u]-1), get(1, 1, n, out[u]+1, n)));
        for(ll v : adj[u])
        {
            if(v == p)continue;
            val.pb(get(1, 1, n, in[v], out[v]));
        }
        if(val.size() > 2)
        {

            if(val[0] * (val[1] + val[2]) > ans)
            {
                ans = val[0] * (val[1] + val[2]);
                for(ll i = 2; i < val.size(); i ++)
                {
                    if(val[i] == val[2])
                    {
                        if(val[0] == val[2])tong = i * (i + 1) / 2 ;
                        else if(val[1] == val[0])tong = (i - 1) * 2;
                        else if(val[1] == val[2])tong = i * (i - 1) / 2;
                        else tong = i - 1;
                    }
                    else break;
                }
            }
            else if(val[0] * ( val[1] + val[2]) == ans)
            {
                for(ll i = 2; i < val.size(); i ++)
                {
                    if(val[i] == val[2])
                    {
                        if(val[0] == val[2])k = i * (i + 1) / 2 ;
                        else if(val[1] == val[0])k = (i - 1) * 2;
                        else if(val[1] == val[2])k = i * (i - 1) / 2;
                        else k = i - 1;
                    }
                    else break;
                }
                tong += k;
            }
        }
    }

    for(ll v : adj[u])
    {
        if(v == p)continue;
        update(1, 1, n, 1, n, 1);
        update(1, 1, n, in[v], out[v], -2);
        dfs2(v, u);
        update(1, 1, n, 1, n, -1);
        update(1, 1, n, in[v], out[v], 2);
    }
}
void sol()
{
    cin >> n;
    for(int i = 1; i < n; i ++)
    {
        ll x, y;
        cin >> x >> y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    tong = 1;
    dfs1(1, 1);
    build(1, 1, n);
    dfs2(1, 1);
    cout << ans << " "<<tong;

}
int main()
{
    if(fopen(task".in", "r"))
    {
       freopen(task".in", "r", stdin);
       freopen(task".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
abba
4
bb
1
aa
10
ab
2
ba
5
*/

Compilation message (stderr)

road.cpp: In function 'void dfs2(long long int, long long int)':
road.cpp:104:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |                 for(ll i = 2; i < val.size(); i ++)
      |                               ~~^~~~~~~~~~~~
road.cpp:118:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |                 for(ll i = 2; i < val.size(); i ++)
      |                               ~~^~~~~~~~~~~~
road.cpp: In function 'int main()':
road.cpp:165:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  165 |        freopen(task".in", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
road.cpp:166:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  166 |        freopen(task".out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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