Submission #343376

#	Time	Username	Problem	Language	Result	Execution time	Memory
343376		emil_physmath	Shymbulak (IZhO14_shymbulak)	C++17	0 / 100	114 ms	11216 KiB

shymbulak

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200'002;
int c[N], used[N];
vector<int> g[N], h;
struct el {
	int l, q;
}mx1[N], mx2[N], dp[N];
vector<el> a;
el operator+(const el& a, const el& b) {
	return { a.l,a.q + b.q };
}
bool operator<(const el& a, const el& b) {
	if (a.l == b.l)
		return a.q < b.q;
	return a.l < b.l;
}
int Dfs(int v, int p) {
	used[v] = 1;
	for(int to: g[v])
		if (to != p) {
			if (used[to]) {
				c[v] = 1;
				h.push_back(v);
				return to;
			}
			int x = Dfs(to, v);
			if (x != 0) {
				c[v] = 1;
				h.push_back(v);
				return (x == v) ? 0 : x;
			}
		}
	return 0;
}
void DfsDp(int v, int p) {
	for (int to : g[v])
		if (to != p && c[to] != 1) {
			DfsDp(to, v);
			el x = { mx1[to].l + 1, mx1[to].q };
			if (x.l > mx1[v].l) {
				mx2[v] = mx1[v];
				mx1[v] = x;
			}
			else if (x.l == mx1[v].l)
				mx1[v].q += x.q;
			else if (x.l > mx2[v].l)
				mx2[v] = x;
			else if (x.l == mx2[v].l)
				mx2[v].q += x.q;
			if (dp[v].l == dp[to].l)
				dp[v] = dp[v] + dp[to];
			if (dp[v].l < dp[to].l)
				dp[v] = dp[to];
		}
	if (!mx1[v].l)
		mx1[v] = {0, 1};
	if (!mx2[v].l)
		mx2[v] = {0, 1};
	el x;
	int sum = 0;
	for (int to : g[v])
		if (to != p && c[to] != 1)
			if (mx1[to].l == mx1[v].l)
				sum += (mx1[v].q - mx1[to].q) * mx1[to].q;
	sum /= 2;
	x = { sum ? el{2 * mx1[v].l, sum / 2} : el{mx1[v].l + mx2[v].l, mx1[v].q * mx2[v].q} };
	if (x.l == dp[v].l && x.l != 0)
		dp[v].q += x.q;
	dp[v] = max(dp[v], x);
    if (!dp[v].l)
        dp[v] = {0, 1};
}
el t[4 * N];
void Build(int v, int vl, int vr)
{
	if (vl == vr)
	{
		t[v] = { a[vl].l,a[vl].q };
		return;
	}
	int m = (vl + vr) / 2;
	Build(v * 2, vl, m);
	Build(v * 2 + 1, m + 1, vr);
	if (t[v * 2].l == t[v * 2 + 1].l)
	{
		t[v].l = t[v * 2].l;
		t[v].q = t[v * 2].q + t[v * 2 + 1].q;
	}
	else t[v] = max(t[v * 2], t[v * 2 + 1]);
}
el GetMax(int v, int vl, int vr, int l, int r)
{
	if (vl == l && vr == r)
		return t[v];
	int m = (vl + vr) / 2;
	el r1, r2;
	if (r <= m)
		return GetMax(v * 2, vl, m, l, r);
	if (l > m)
		return GetMax(v * 2 + 1, m + 1, vr, l, r);
	r1 = GetMax(v * 2, vl, m, l, m);
	r2 = GetMax(v * 2 + 1, m + 1, vr, m + 1, r);
	if (r1.l == r2.l)
		return { r1.l,r1.q + r2.q };
	return max(r1, r2);
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	Dfs(1, -1);
	el ans = { 0,1 };
	for (int i = 1; i <= n; i++) {
		if (c[i]) {
			DfsDp(i, -1);
		}
	//	cerr << "dp" << i << ' ' << dp[i].l << ' ' << dp[i].q << '\n';
		//cerr << "ans " << ans.l << ' ' << ans.q << '\n';
	}
	for (int i = 1; i <= n; i++)
        if (dp[i].l == ans.l)
            ans.q += dp[i].q;
        else
            ans = max(ans, dp[i]);
	for (int v : h)	{
	//	cerr << v << ' ';
		a.push_back(mx1[v]);
	}
	//cerr << '\n';
	for (int v : h) {
		//cerr << mx1[v].l << ' ';
		a.push_back(mx1[v]);
	}
	//cerr << '\n';
	//for (auto v : a)
		//cerr << v.l << ' ';
	//cerr << '\n';
	n = (int)a.size() / 2;
	for (int i = 0; i < a.size(); i++) {
		a[i].l += i;
	//	cerr << a[i].l << ' ' << a[i].q << '\n';
		//if (a[i].q == 0)a[i].q++;
	}
	//cerr << '\n';
	Build(1, 0, (int)a.size() - 1);
	//cerr << "ans " << ans.l << ' ' << ans.q << '\n';
	for (int i = 0; i < n; i++) {
		el cur = GetMax(1, 0, 2 * n - 1, i + 1, i + n / 2);
		//cerr << i + 1 << "..." << i + n / 2 << "..." << cur.l << ' ' << cur.q << '\n';
		cur.l -= 2 * i;
		cur.l += a[i].l;
		cur.q *= a[i].q;
		//cerr << i + 1 << "..." << i + n / 2 << "..." << cur.l << ' ' << cur.q << "\n\n";
		if (cur.l == ans.l)
			ans.q += cur.q;
		else ans = max(ans, cur);
	}
	cout << ans.q << '\n';
	return 0;
}
/*#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 200'002;
int c[N], used[N];
vector<int> g[N];
struct el {
	int l, q;
}mx1[N], mx2[N], dp[N];
el operator+(const el& a, const el& b)
{
	return { a.l,a.q + b.q };
}
bool operator<(const el& a, const el& b)
{
	if (a.l == b.l)
		return a.q < b.q;
	return a.l < b.l;
}
int Dfs(int v, int p)
{
	used[v] = 1;
	for(int to: g[v])
		if (to != p)
		{
			if (used[to])
			{
				c[v] = 1;
				return to;
			}
			int x = Dfs(to, v);
			if (x != 0)
				c[x] = 1;
			return (x == v) ? 0 : x;
		}
	return 0;
}
void DfsDp(int v, int p)
{
	for(int to: g[v])
		if (to != p && c[to] != 1)
		{
			DfsDp(to, v);
			if (mx1[to].l + 1 >= mx1[v].l)
			{
				mx2[v] = mx1[v];
				mx1[v] = { mx1[to].l + 1,mx1[to].q };
			}
			else if (mx1[to].l + 1 >= mx2[v].l)
				mx2[v] = { mx1[to].l + 1,(mx1[to].l + 1 > mx2[v].l) ? mx1[to].q : max(mx1[to].q,mx2[to].q) };
			if (dp[v].l == dp[to].l)
				dp[v] = dp[v] + dp[to];
			if (dp[v].l < dp[to].l)
				dp[v] = dp[to];
		}
	int s1 = 0, s2 = 0;
	for (int to : g[v])
		if (to != p && c[to] != 1)
		{
			if (mx1[to].l + 1 == mx1[v].l)
				s1 += mx1[to].q;
			if (mx1[to].l + 1 == mx2[v].l)
				s2 += mx1[to].q;
		}
	el x;
	if (mx1[v].l != mx2[v].l)
		x = { mx1[v].l + mx2[v].l,s1 * s2 };
	else
	{
		s2 = 0;
		for (int to : g[v])
			if (to != p && c[to] != 1)
				if (mx1[to].l + 1 == mx1[v].l)
					s2 += (s1 - mx1[to].q) * mx1[to].q;
		x = { 2 * mx1[v].l,s2 };
	}
	if (x.l == dp[v].l)
		dp[v].q += s1 * s2;
	dp[v] = max(dp[v], x);
}
int main()
{
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	Dfs(1, -1);
	for (int i = 1; i <= n; i++)
		if (c[i])
			DfsDp(i, -1);
	return 0;
}*/
/*#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <random>
#include <chrono>
#include <queue>
#include <tuple>
#include <set>
using namespace std;
#ifdef MANSON
#define BUGO(x) cerr << #x << " = " << (x) << '\n';
#define BUGOARR(a) cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';
ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
    return out << "{" << p.first << ", " << p.second << "}";
}
#else
#define BUGO(x)
#define BUGOARR(a)
#endif
using llong = long long;
using uint = unsigned int;
using ullong = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }

int main()
{
    pair<int, int> p = {70, 70};
    int a, b;
    tie(a, b) = p;
    --a; --b;
    cout << p;
    exit(0);
    ios::sync_with_stdio(0);
    cin.tie(0);
    int ans = 0;
    for (int mask = 0; mask < 1 << 17; ++mask)
    {
        int n = __builtin_popcount(mask);
        ans += n * (n - 1) / 2;
    }
    cout << ans * 17;
}*/
/*#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <random>
#include <chrono>
#include <set>
using namespace std;
#ifdef MANSON
#define BUGO(x) cerr << #x << " = " << (x) << '\n';
#define BUGOARR(a) cerr << #a << ": "; for (auto i: a) cerr << i << ' '; cerr << '\n';
ostream& operator<<(ostream& out, const pair<auto, auto>& p) {
    return out << "{" << p.first << ", " << p.second << "}";
}
#else
#define BUGO(x)
#define BUGOARR(a)
#endif
using llong = long long;
using uint = unsigned int;
using ullong = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l, int r) { return uniform_int_distribution<int>(l, r)(rng); }
const int mod = 1000'000'007;
const int maxN = 305;

int C[maxN][maxN], fact[maxN];
int dp[maxN][maxN][maxN], finDp[maxN][maxN], ans[maxN], smAhead[maxN], bigAhead[maxN];

inline void Mod(int& x) { if (x >= mod) x -= mod; }
inline llong binpow(llong a, llong p) {
    if (p == 0) return 1;
    if (p % 2) return (binpow(a, p - 1) * a) % mod;
    return binpow((a * a) % mod, p / 2);
}
inline llong Mult(llong a, llong b = 1, llong c = 1, llong d = 1) {
    a *= b; a %= mod;
    a *= c; a %= mod;
    a *= d; a %= mod;
    return a;
}
void F(int a[][10])
{
    ++a[0][0];
}
int main()
{
    for (int n = 0; n < maxN; ++n) {
        fact[n] = (n ? Mult(fact[n - 1], n) : 1);
        C[n][0] = C[n][n] = 1;
        for (int k = 1; k < n; ++k) {
            C[n][k] = C[n - 1][k - 1] + C[n - 1][k];
            Mod(C[n][k]);
        }
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int& i: a) cin >> i;
    vector<int> srtInd(n);
    auto b = a;
    sort(b.begin(), b.end());
    for (int i = 0; i < n; ++i)
        srtInd[i] = lower_bound(b.begin(), b.end(), a[i]) - b.begin();

    for (int small = 0; small <= k; ++small)
        dp[k - 1][small][small] = C[k][small];
    for (int i = k - 1; i + 1 < n; ++i)
        for (int sm = 1; sm <= i + 1; ++sm)
            for (int smK = 1; smK <= k && smK <= sm; ++smK)
            {
                dp[i + 1][sm][smK - 1] += dp[i][sm][smK];
                Mod(dp[i + 1][sm][smK - 1]);
                dp[i + 1][sm + 1][smK] += dp[i][sm][smK];
                Mod(dp[i + 1][sm + 1][smK]);
            }
    for (int i = k - 1; i < n; ++i)
        for (int sm = 0; sm <= i + 1; ++sm)
            finDp[i][sm] = dp[i][sm][0];
    for (int i = k - 1; i + 1 < n; ++i)
        for (int sm = 0; sm <= i + 1; ++sm) {
            finDp[i + 1][sm] += finDp[i][sm];
            Mod(finDp[i + 1][sm]);
            finDp[i + 1][sm + 1] += finDp[i][sm];
            Mod(finDp[i + 1][sm + 1]);
        }
    for (int x = 0; x < n; ++x)
    {
        for (int i = k - 1; i < n; ++i)
            for (int sm = 0; sm < i + 1; ++sm) {
                if (sm > x) continue;
                if (i + 1 - sm > n - x) continue;
                smAhead[x] += Mult(Mult(i + 1 - sm, dp[i][sm][0], sm, C[n - 1 - i][x - sm]), fact[x], fact[n - 1 - x]);
                Mod(smAhead[x]);
            }
        for (int i = k; i < n; ++i)
            for (int sm = 1; sm <= i; ++sm) {
                if (sm > x) continue;
                if (i - sm > n - x - 1) continue;
                smAhead[x] += Mult(Mult(finDp[i - 1][sm], sm), C[n - 1 - i][x - sm], fact[x], fact[n - x - 1]);
                Mod(smAhead[x]);
            }
        for (int smK = 1; smK <= k && smK <= x; ++smK) {
            smAhead[x] += Mult(dp[n - 1][x][smK], x, fact[x], fact[n - x]);
            Mod(smAhead[x]);
        }
    }
    for (int x = 0; x < n; ++x)
    {
        for (int y = 0; y < n; ++y)
            if (y != x) {
                int ahead = srtInd[y] < srtInd[x] ?
                    Mult(smAhead[srtInd[x]], binpow(srtInd[x], mod - 2)) :
                    (fact[n] - Mult(smAhead[srtInd[y]], binpow(srtInd[y], mod - 2)) + mod) % mod;
                if (srtInd[y] > srtInd[x]) {
                    bigAhead[x] += ahead;
                    Mod(bigAhead[x]);
                }
                ans[x] += Mult(ahead, a[y]);
                Mod(ans[x]);
            }
        ans[x] += Mult(a[x], fact[n]);
        Mod(ans[x]);
    }

    for (int i = 0; i < n; ++i)
        cout << Mult(ans[i], bigAhead[i]) << ' ';
}
*/

Compilation message (stderr)

shymbulak.cpp: In function 'int main()':
shymbulak.cpp:148:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<el>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~

• Subtask 1: 0 / 30
• Subtask 2: 0 / 20
• Subtask 3: 0 / 50