Submission #501789

#	Time	Username	Problem	Language	Result	Execution time	Memory
501789		betatester22	Shymbulak (IZhO14_shymbulak)	C++14	100 / 100	148 ms	27324 KiB

shymbulak

#include <cstdio>
#include <vector>

const int N = 200000;
std::vector<int> g[N], c;
int n;
bool u[N], cyc[N];

int go(int v, int pr = -1) 
{
	u[v] = 1;
	for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr) {
		if (u[g[v][i]]) {
			cyc[v] = 1;
			cyc[g[v][i]] = 1;
			c.push_back(g[v][i]);
			c.push_back(v);
			return 1;
		}
		int k;
		if (k = go(g[v][i], v)) {
			if (k == -1 || c.front() == v) return -1;
			cyc[v] = 1;
			c.push_back(v);
			return 1;
		}
	}
	return 0;
}

struct item {
	int max;
	long long amt;
	item(int max_ = (1 << 31) >> 2, long long amt_ = 0) {
		max = max_;
		amt = amt_;
	}
	item operator+(item arg) {
		item res;
		res.max = std::max(max, arg.max);
		if (res.max == max) res.amt += amt;
		if (res.max == arg.max) res.amt += arg.amt;
		return res;
	}
} t[N << 2];

item fres;
int last;
void far(int v, int cur = 0, int pr = -1) 
{
	fres = fres + item(cur, 1);
	if (fres.max == cur) last = v;
	for (int i = 0; i < (int)g[v].size(); ++i) if (g[v][i] != pr && !cyc[g[v][i]]) far(g[v][i], cur + 1, v);
}

std::vector<int> path;
bool find(int v, int d, int pr = -1) 
{
	if (!d) {
		path.push_back(v);
		return 1;
	}
	for (int i = 0; i < (int)g[v].size(); ++i) if (!cyc[g[v][i]] && g[v][i] != pr && find(g[v][i], d - 1, v)) {
		path.push_back(v);
		return 1;
	}
	return 0;
}

item get(int l, int r) 
{
	item res;
	for (l += c.size() << 1, r += c.size() << 1; l < r; l >>= 1, r >>= 1) {
		if (l & 1) res = res + t[l++];
		if (r & 1) res = res + t[--r];
	}
	return res;
}

int main() 
{
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		int a, b;
		scanf("%d%d", &a, &b);
		g[a - 1].push_back(b - 1);
		g[b - 1].push_back(a - 1);
	}
	go(0);
	item ans;
	for (int i = 0; i < (int)c.size(); ++i) {
		cyc[c[i]] = 0;
		fres = item();
		far(c[i]);
		fres.max -= i;
		t[c.size() * 2 + i] = fres;
		fres.max -= c.size();
		t[c.size() * 3 + i] = fres;
		int from = last;
		fres = item();
		far(last);
		path.clear();
		find(from, fres.max);
		item cur;
		cur.max = path.size() - 1;
		if (path.size() & 1) {
			int c = path[(int)path.size() >> 1];
			cyc[c] = 1;
			int amt = 0;
			for (int i = 0; i < (int)g[c].size(); ++i) if (!cyc[g[c][i]]) {
				fres = item();
				far(g[c][i]);
				if (fres.max + 1 == path.size() / 2) {
					cur.amt += fres.amt * amt;
					amt += fres.amt;
				}
			}
			cyc[c] = 0;
		} else {
			int u = path[path.size() >> 1], v = path[path.size() - 1 >> 1];
			fres = item();
			far(u, 0, v);
			int amt = fres.amt;
			fres = item();
			far(v, 0, u);
			cur.amt = fres.amt * amt;
		}
		ans = ans + cur;
		cyc[c[i]] = 1;
	}
	for (int i = (int)c.size() * 2 - 1; i; --i) t[i] = t[i << 1 | 1] + t[i << 1];
	for (int i = 0; i < (int)c.size(); ++i) {
		item cur = get((c.size() + 1 >> 1) + i, c.size() + i);
		cur.max += c.size() + i + t[c.size() * 2 + i].max + i;
		cur.amt *= t[2 * c.size() + i].amt;
		ans = ans + cur;
	}
	printf("%lld\n", ans.amt);
	return 0;
}

Compilation message (stderr)

shymbulak.cpp: In function 'int go(int, int)':
shymbulak.cpp:21:9: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   21 |   if (k = go(g[v][i], v)) {
      |       ~~^~~~~~~~~~~~~~~~
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:113:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     if (fres.max + 1 == path.size() / 2) {
      |         ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~
shymbulak.cpp:120:57: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
  120 |    int u = path[path.size() >> 1], v = path[path.size() - 1 >> 1];
      |                                             ~~~~~~~~~~~~^~~
shymbulak.cpp:133:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |   item cur = get((c.size() + 1 >> 1) + i, c.size() + i);
      |                   ~~~~~~~~~^~~
shymbulak.cpp:82:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   82 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
shymbulak.cpp:85:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

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