oj.uz

답안 #1052693

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1052693 2024-08-10T19:34:32 Z _rain_ Roadside Advertisements (NOI17_roadsideadverts) C++14
30 / 100
 48 ms 11548 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

const int maxn = 5e4;
const int maxlog = 14;
vector<pair<int,int>> g[maxn+2];
int sta[maxn+2] , fin[maxn+2] , timedfs = 0 , n;
int par[maxn+2][maxlog+2] , h[maxn+2] , v[maxn+2] , d[maxn+2];

	void dfs(int u , int p)
	{
		sta[u] = ++timedfs;
		h[u] = h[p]+1;
		par[u][0] = p;
		for (int i = 1; i <= maxlog; ++i)
			par[u][i] = par[par[u][i - 1]][i - 1];
		for (auto& v : g[u])
			if(v.first != p)
			{
				d[v.first] = d[u] + v.second;
				dfs(v.first , u);
			}
		fin[u] = timedfs;
		return;
	}
	int LCA(int u , int v)
	{
		if (h[u] < h[v]) swap(u,v);
		for (int i = maxlog; i >= 0; --i)
			if (h[par[u][i]] >= h[v])
				u = par[u][i];
		if (u==v) return u;
		for (int i = maxlog; i >= 0; --i)
			if (par[u][i]!=par[v][i])
				u = par[u][i] , v = par[v][i];
		return par[u][0];
	}
bool parent(int u , int lca)
{
	return sta[lca] <= sta[u] && sta[u] <= fin[lca];
}

bool cmp(int x , int y)
{
	return sta[x] < sta[y];
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	#define name "main"
	if (fopen(name".inp","r"))
	{
		freopen(name".inp","r",stdin);
		freopen(name".out","w+",stdout);
	}
	cin >> n;
	for (int i = 1; i < n; ++i)
			{
				int u , v , w; cin >> u >> v >> w;
				++u,++v;
				g[u].push_back({v,w});
				g[v].push_back({u,w});
			}
	dfs(1,0);
	int q; cin >> q;
	while(q--)
	{
		int numv = 5;
		vector<int> vert;
		for (int i = 1; i <= numv; ++i) {
			cin >> v[i]; ++v[i];
			vert.push_back(v[i]);
		}
		sort(v+1,v+numv+1,cmp);
		for (int i = 2;i <= numv; ++i) vert.push_back(LCA(v[i],v[i-1]));
		sort(vert.begin(),vert.end(),cmp); vert.resize(unique(vert.begin(),vert.end()) - vert.begin());
		vector<int> lis;
		i64 answer = 0;
		lis.push_back(vert[0]);
		for (int i = 1; i < vert.size(); ++i)
		{
			while (lis.size() && !parent(vert[i],lis.back())) lis.pop_back();
			if (lis.size())
			{
				// cout << lis.back() << ' ' << vert[i] << '\n';
				answer += d[vert[i]] - d[lis.back()];
			}
			lis.push_back(vert[i]);
		}
		cout << answer << '\n';
	}
}

Compilation message

roadsideadverts.cpp: In function 'int main()':
roadsideadverts.cpp:83:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |   for (int i = 1; i < vert.size(); ++i)
      |                   ~~^~~~~~~~~~~~~
roadsideadverts.cpp:56:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |   freopen(name".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:57:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |   freopen(name".out","w+",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5468 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 10076 KB Output is correct
2 Correct 25 ms 11356 KB Output is correct
3 Correct 26 ms 11352 KB Output is correct
4 Correct 26 ms 11356 KB Output is correct
5 Correct 25 ms 11356 KB Output is correct
6 Correct 29 ms 11548 KB Output is correct
7 Correct 27 ms 11356 KB Output is correct
8 Correct 48 ms 11356 KB Output is correct
9 Correct 30 ms 11356 KB Output is correct
10 Correct 47 ms 11352 KB Output is correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8280 KB Output is correct
2 Incorrect 18 ms 10588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 5468 KB Output is correct
2 Correct 26 ms 10076 KB Output is correct
3 Correct 25 ms 11356 KB Output is correct
4 Correct 26 ms 11352 KB Output is correct
5 Correct 26 ms 11356 KB Output is correct
6 Correct 25 ms 11356 KB Output is correct
7 Correct 29 ms 11548 KB Output is correct
8 Correct 27 ms 11356 KB Output is correct
9 Correct 48 ms 11356 KB Output is correct
10 Correct 30 ms 11356 KB Output is correct
11 Correct 47 ms 11352 KB Output is correct
12 Correct 12 ms 8280 KB Output is correct
13 Incorrect 18 ms 10588 KB Output isn't correct
14 Halted 0 ms 0 KB -