제출 #36798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
36798		alenam0161	관광지 (IZhO14_shymbulak)	C++14	0 / 100	163 ms	61480 KiB

shymbulak

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <deque>
using ll = long long;
using namespace std;
const int N = 2000 * 100 + 7;
typedef vector<ll> vi;
typedef vector<vi> vp;
typedef vector<bool> vb;
#define ad push_back
#define mp make_pair
int n;

struct vt {
	ll vl, how;
	int vertex;
	vt() {}
	vt(ll x,ll e=1,int _v=0) {
		vl = x; how = e; vertex = _v;
	}
	void operator +=(const vt &A){
		if (A.vl == vl)how += A.how;
		else if (A.vl > vl)*this = A;
	}
	vt operator+(const ll &c)const {
		return vt(vl + c, how,vertex);
	}
}ans;
typedef vector<vt> vat;
bool only[N];
vi cur,ham;
int timer = 0;
int up[N];
struct graph {
	int len;
	vp g;
	vi loop;
	vb used;
	vi par;
	vt dp;
	vi road;
	vat mas;
	bool find_loop;
	void write() {
		cout << len <<'\t'<<"Number of edges"<< endl;
		for (int i = 1; i <= len; ++i) {
			for (int to : g[i]) {
				cout <<"form  " <<i << "  to " << to << endl;
			}
		}
		cout << "LOOOP" << endl;
		for (int to : loop) {
			cout << to << " ";
		}
		cout << endl;
	}
	void resize(int n) {
		find_loop = false;
		len = n;
		g.ad(vi());
		used.resize(n + 2);
		par.resize(n + 2);
		for (int i = 1; i <= len; ++i) {
			g.ad(vi());
			used[i] = false;
			par[i] = 0;
		}
	}
	void clear() {
		for (int i = 0; i <= len; ++i)used[i] = false;
	}
	void read() {
		scanf("%d", &len);
		resize(len);
		for (int i = 1; i <= len; ++i) {
			int u, v;
			scanf("%d%d", &u, &v);
			g[v].ad(u);
			g[u].ad(v);
		}
	}
	ll dfs_size(int v, int p = -1) {
		ll w = 1;
		if (p == -1) {
			cur.ad(v); ham.ad(++timer);
			up[v] = timer;
		}
		for (int to : g[v]) {
			if (to == p || only[to])continue;
			cur.ad(to); ham.ad(++timer);
			up[to] = timer;
			w += dfs_size(to, v);
		}
		return w;
	}
	void dfs_for_loop(int v,int p=-1) {
		if (find_loop)return;
		used[v] = true;
		par[v] = p;
		for (int to : g[v]) {
			if (to == p)continue;
			if (find_loop)continue;
			if (used[to]) {
				int e = v;
				while (true) {
					loop.ad(e);
					if (e == to)break;
					e = par[e];
				}
				find_loop = true;
			}
			else {
				dfs_for_loop(to, v);
			}
		}
	}
	void cycle() {
		clear();
		dfs_for_loop(1, 1);
	}
	void build_MAIN() {
		cycle();
		for (int to :loop)only[to] = true;
	}
	vt dfs_find(int v, int p = -1) {
		vt d=vt(0,1,v);
		for (int to : g[v]) {
			if (to == p)continue;
			if (used[to])continue;
			d +=dfs_find(to, v)+1;
		}
		return d;
	}
	void dfs_find_road(int v, int k, int p) {
		if (find_loop)return;
		par[v] = p;
		for (int to : g[v]) {
			if (find_loop)break;
			if (to == p)continue;
			if (to == k) {
				int e = to;
				par[to] = v;
				while (true) {
					road.ad(e);
					if (e == par[e])break;
					e = par[e];
				}
				find_loop = true;
				break;
			}
			dfs_find_road(to, k, v);
		}
	}
	void solve() {
		for (int i = 0; i <= len; ++i)if (used.size() == i)used.ad(0); else used[i] = 0;
		vt a = dfs_find(1);
		int g1 = a.vertex;
		dp = a;
		a = dfs_find(g1);
		int g2 = a.vertex;
		find_loop = 0;
		dfs_find_road(g1, g2,g1);
		for (int to : road)used[to] = true;
		mas.resize(len + 1);
		for (int i = 0; i < road.size(); ++i) {
			mas[i] = vt();
		}
		for (int i = 0; i < road.size(); ++i) {
			mas[i] = dfs_find(road[i]);
		}
		int sz = road.size();
		vt res = vt(sz - 1, 1, 0);
		for (int i = 1; i < sz - 1; ++i) {
			ll qan = 2;
			if (mas[i].vl == i&&i == sz - i - 1) {
				for (int to : g[road[i]]) {
					used[to] = true;
					used[road[i]] = true;
					vt r = dfs_find(to);
					if (r.vl == i - 1) {
						res.how += qan*r.how;
						qan++;
					}
				}
			}
			else {
				if (mas[i].vl == i) {
					res.how += mas[i].how;
				}
				if (mas[i].vl == sz - i - 1) {
					res.how += mas[i].how;
				}
			}
		}
		ans += res;
	}
}gr[N],root;

void dfs_creat(int s, int v, int p = -1) {
	for (int to : root.g[v]) {
		if (to == p || only[to])continue;
		gr[s].g[up[v]].ad(up[to]);
		gr[s].g[up[to]].ad(up[v]);
		dfs_creat(s, to, v);
	}
}
deque<vt> q;
void add(ll x, ll hw) {
	while (q.size() > 0 && q.back().vl <= x) {
		hw += q.back().how; q.pop_back();
	}
	q.push_back(vt(x, hw));
}
void remove(ll hw) {
	q.front().how -= hw;
	if (q.front().how == 0)q.pop_front();
}
int main() {
	//freopen("Text1.txt", "r", stdin);
	memset(only, 0, sizeof(only));
	root.read();
	root.build_MAIN();
	int sz = 0;
	for (int i = 0; i < root.loop.size(); ++i) {
		for (int to : cur)up[to] = 0;
		cur.clear(); ham.clear(); timer = 0;
		int e = root.dfs_size(root.loop[i]);
		gr[sz].resize(e);
		dfs_creat(sz, root.loop[i]);
		sz++;
	}
	for (int i = 0; i < sz; ++i) {
		gr[i].solve();
	}
	ll f = 0;
	int siz = root.loop.size();
	if (siz% 2 == 0) {
		add(gr[0].dp.vl, gr[0].dp.how);
		f++;
		int k = siz / 2;
		int qr = 1;
		for (int i = 1; i < siz+k; ++i) {
			if (qr > k)remove(gr[(i - k - 1+siz)%siz].dp.how);
			qr++;
			ans += vt(q.front().vl + f+gr[i%siz].dp.vl, q.front().how*gr[i%siz].dp.how);
			add(gr[i%siz].dp.vl - f, gr[i%siz].dp.how);
			f++;
		}
	}
	else {
		add(gr[0].dp.vl, gr[0].dp.how);
		f++;
		int k = siz / 2;
		int qr = 1;
		for (int i = 1; i < siz + k; ++i) {
			if (qr > k)remove(gr[(i - k - 1 + siz) % siz].dp.how);
			qr++;
			ans += vt(q.front().vl + f+gr[i%siz].dp.vl, q.front().how*gr[i%siz].dp.how);
			add(gr[i%siz].dp.vl - f, gr[i%siz].dp.how);
			f++;
		}
	}
	cout << ans.how << endl;
	return 0;
}

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

shymbulak.cpp: In member function 'void graph::solve()':
shymbulak.cpp:160:49: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i <= len; ++i)if (used.size() == i)used.ad(0); else used[i] = 0;
                                                 ^
shymbulak.cpp:170:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < road.size(); ++i) {
                     ^
shymbulak.cpp:173:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 0; i < road.size(); ++i) {
                     ^
shymbulak.cpp: In function 'int main()':
shymbulak.cpp:229:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < root.loop.size(); ++i) {
                    ^
shymbulak.cpp: In member function 'void graph::read()':
shymbulak.cpp:78:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &len);
                    ^
shymbulak.cpp:82:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d%d", &u, &v);
                         ^

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