제출 #525265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
525265		keta_tsimakuridze	Designated Cities (JOI19_designated_cities)	C++14	100 / 100	1625 ms	60584 KiB

designated_cities

#include<bits/stdc++.h>
#define int long long
#define f first
#define s second
#define pii pair<int,int>
#define Pii pair<int,pii>
using namespace std;
const int N = 2e5 + 5, mod = 1e9 + 7; // !
int t, h[N], g[N], ans[N], sz[N], n, vis[N], f[N], all[N], oneway;
pii par[N];
vector<pii> x;
vector<Pii> V[N];
void dfs(int u,int p,int s) {
	g[u] = s; 
	x.push_back({h[u], u});
	for(int i = 0; i < V[u].size(); i++) {
		int v = V[u][i].f;
		if(v== p || f[v]) continue;
		h[v] = h[u] + V[u][i].s.f;
		par[v] = {u, V[u][i].s.f};
		dfs(v, u, s);
	}
}
void dfs(int u,int p) {
	sz[u] = 0;
	for(int i = 0; i < V[u].size(); i++) {
		int v = V[u][i].f;
		if(v== p || f[v]) continue;
		dfs(v, u);
		sz[u] += sz[v];
	}
	sz[u]++;
}
int find(int u,int p, int Sz) {
	for(int i = 0; i < V[u].size(); i++) {
		int v = V[u][i].f;
		if(v== p || f[v]) continue;
		if(sz[v] > Sz/2) return find(v, u, Sz);
	}	
	return u;
}
int up(int u,int c) {
	int dep = 0;
	while(!(vis[u] == c)) {
		dep += par[u].s; 
		vis[u] = c;
		u = par[u].f;
	}
	return dep;
}
void decomp(int U) {
	dfs(U, 0);
	int c = find(U, 0, sz[U]);
	f[c] = 1;
	g[c] = 0;
	x.clear();
	
	for(int i = 0; i < V[c].size(); i++) {
		int v = V[c][i].f;
		if(f[v]) continue;
		h[v] = V[c][i].s.f;
		dfs(v, c, v);
		par[v] = {h[v], c};
		swap(par[v].f, par[v].s);
	}
	x.push_back({0, c});
	sort(x.rbegin(), x.rend());
	vector<pii> y;
	vis[c] = c;
	for(int i = 0; i < x.size(); i++) {
		int u = x[i].s;
		y.push_back({up(u, c), u});
	}
	sort(y.rbegin(), y.rend());
	int id = 0;
	for(int i = 0; i < y.size(); i++) {
		if(g[y[i].s] != g[y[0].s]) {
			id = i;
			break;
		}
	}
	ans[2] = max(ans[2], all[c] + y[0].f + y[id].f);
	int p = all[c] + y[0].f + y[id].f, cnt = 2;
	for(int i = 1; i < y.size(); i++) {
		if(i == id) continue;
		cnt++;
		p += y[i].f;
		ans[cnt] = max(ans[cnt], p);
	}
//	return;
	for(int i = 0; i < V[c].size(); i++) {
		if(!f[V[c][i].f]) decomp(V[c][i].f);
	}
}
void dfs1(int u,int p) {
	for(int i = 0; i < V[u].size(); i++) {
		int v = V[u][i].f;
		if(v == p) continue;
		dfs1(v, u);
		oneway += V[u][i].s.s;
	}
}
void dfs2(int u,int p) { 
	all[u] = oneway;
	ans[1] = max(ans[1], oneway);
	for(int i = 0; i < V[u].size(); i++) {
		int v = V[u][i].f;
		if(v == p) continue;
		oneway -= V[u][i].s.s;
		oneway += V[u][i].s.f;
		dfs2(v, u);
		oneway -= -V[u][i].s.s;
		oneway += -V[u][i].s.f;		
	}
}
main(){
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n;
	int MS = 0;
	for(int i = 2; i <= n; i++) {
		int u,v,w ,a , b;
		cin >> u >> v >> a >> b;
		V[u].push_back({v, {a, b}});
		V[v].push_back({u, {b, a}});
		MS += a + b;
	}
	dfs1(1, 0);
	dfs2(1, 0);
	decomp(1);
	int q; cin >> q;
	while(q--) {
		int c; cin >> c;
		cout << MS - ans[c] << " ";
	}
}

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

designated_cities.cpp: In function 'void dfs(long long int, long long int, long long int)':
designated_cities.cpp:16:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs(long long int, long long int)':
designated_cities.cpp:26:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'long long int find(long long int, long long int, long long int)':
designated_cities.cpp:35:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void decomp(long long int)':
designated_cities.cpp:58:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |  for(int i = 0; i < V[c].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp:70:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
designated_cities.cpp:76:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |  for(int i = 0; i < y.size(); i++) {
      |                 ~~^~~~~~~~~~
designated_cities.cpp:84:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |  for(int i = 1; i < y.size(); i++) {
      |                 ~~^~~~~~~~~~
designated_cities.cpp:91:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0; i < V[c].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs1(long long int, long long int)':
designated_cities.cpp:96:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: In function 'void dfs2(long long int, long long int)':
designated_cities.cpp:106:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |  for(int i = 0; i < V[u].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
designated_cities.cpp: At global scope:
designated_cities.cpp:116:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  116 | main(){
      | ^~~~
designated_cities.cpp: In function 'int main()':
designated_cities.cpp:121:11: warning: unused variable 'w' [-Wunused-variable]
  121 |   int u,v,w ,a , b;
      |           ^

• Subtask 1: 6 / 6
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 17 / 17
• Subtask 5: 17 / 17
• Subtask 6: 44 / 44