oj.uz

Submission #397846

# Submission time Handle Problem Language Result Execution time Memory
397846 2021-05-03T09:32:54 Z maomao90 Roadside Advertisements (NOI17_roadsideadverts) C++14
70 / 100
 1000 ms 12116 KB 
#include <cstdio>
#include <vector>
#include <cstring>
#include <utility>
#include <algorithm>
#include <set>
#include <tuple>

using namespace std;

typedef pair <int, int> ii;
typedef tuple <int, int, int> iii;

#define INF 1000000005

//#define DEBUG

class UnionFind
{
private:
    vector <int> p, ranks;
public:
    void initialise(int n)
    {
        p.assign(n, 0); ranks.assign(n, 1);
        for (int i = 0; i < n; i++) p[i] = i;
    }
    int findSet(int a)
    {
        if (p[a] == a) return a;
        return p[a] = findSet(p[a]);
    }
    bool isSameSet(int a, int b)
    {
        return findSet(a) == findSet(b);
    }
    void unionSet(int a, int b)
    {
        if (!isSameSet(a, b))
        {
            int pa = findSet(a), pb = findSet(b);
            if (ranks[pa] < ranks[pb]) p[pa] = pb;
            else
            {
                p[pb] = pa;
                if (ranks[pa] == ranks[pb])
                {
                    ranks[pa]++;
                }
            }
        }
    }
};

int V, Q;
vector <ii> adjList[50005];
int sponsors[5];
bool isSponsor[50005];
int level[50005];
int dist[50005];
int p[20][50005];

int adjMatrix[50][50];
vector <iii> edgeList;
set <int> processing;
vector <int> vertices;
UnionFind UF;
int ans;

int LCA(int a, int b)
{
	if (level[a] < level[b]) swap(a, b);
	for (int i = 19; i >= 0; i--)
	{
		if (level[p[i][a]] >= level[b] && p[i][a] != -1)
		{
			a = p[i][a];
		}
	}

	if (a == b) return a;

	for (int i = 19; i >= 0; i--)
	{
		if (p[i][a] != p[i][b])
		{
			a = p[i][a]; b = p[i][b];
		}
	}
	return p[0][a];
}

void root(int source, int prevDist, int prevLvl, int prevP)
{
	dist[source] = prevDist;
	p[0][source] = prevP;
	level[source] = prevLvl;
	for (ii neighbour : adjList[source])
	{
		if (neighbour.first != prevP)
		{
			root(neighbour.first, prevDist + neighbour.second, prevLvl + 1, source);
		}
	}
}

int main()
{
	scanf("%d", &V);
	for (int i = 0; i < V-1; i++)
	{
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		adjList[u].emplace_back(v, w);
		adjList[v].emplace_back(u, w);
	}
	memset(p, -1, sizeof(p));
	root(0, 0, 0, -1);

	for (int k = 1; k < 20; k++)
	{
		for (int i = 0; i < V; i++)
		{
			if (p[k-1][i] != -1)
			{
				p[k][i] = p[k-1][p[k-1][i]];
			}
			else p[k][i] = -1;
		}
	}

	#ifdef DEBUG
	printf("Parent:\n");
	for (int i = 0; i < 20; i++)
    {
        printf("k=%d:", i);
        for (int j = 0; j < V; j++)
        {
            printf(" %d", p[i][j]);
        }
        printf("\n");
    }
    printf("\n");
	#endif // DEBUG

	scanf("%d", &Q);
	for (int i = 0; i < Q; i++)
	{
		memset(isSponsor, false, sizeof(isSponsor));
		for (int j = 0; j < 5; j++)
		{
			scanf("%d", sponsors + j);
			isSponsor[sponsors[j]] = true;
		}

		edgeList.clear();
		processing.clear();
		vertices.clear();
//		for (int j = 0; j < 30; j++) for (int k = 0; k < 30; k++) {
//			adjMatrix[j][k] = INF;
//		}
		for (int j = 0; j < 5; j++)
		{
			int cnt = 0;
			for (int k = j + 1; k < 5; k++)
			{
			    int temp = LCA(sponsors[j], sponsors[k]);
				processing.insert(temp);
				// adjMatrix[sponsors[j]][temp] = adjMatrix[temp][sponsors[j]] = dist[sponsors[j]] - dist[temp];
				// adjMatrix[k][temp] = adjMatrix[temp][k] = dist[k] - dist[temp];
			    // edgeList.emplace_back(dist[sponsors[j]] - dist[temp], sponsors[j], temp);
			    // edgeList.emplace_back(dist[k] - dist[temp], k, temp);
			}
			processing.insert(sponsors[j]);
		}

		for (auto &i : processing) vertices.push_back(i);
		for (int j = 0; j < vertices.size(); j++) {
			for (int k = j + 1; k < vertices.size(); k++) {
				int tempj = vertices[j], tempk = vertices[k];
				int lca = LCA(tempj, tempk);
				edgeList.emplace_back(dist[tempj] + dist[tempk] - 2 * dist[lca], tempj, tempk);
			}
		}
//		for (int l = 0; l < 30; l++) for (int j = 0; j < 30; j++) for (int k = 0; k < 30; k++) {
//			adjMatrix[j][k] = min(adjMatrix[j][k], adjMatrix[j][l] + adjMatrix[l][k]);
//		}
//		for (int j = 0; j < 30; j++) for (int k = 0; k < 30; k++) {
//			if (adjMatrix[j][k] != INF) {
//				edgeList.emplace_back(adjMatrix[j][k], j, k);
//			}
//		}
		sort(edgeList.begin(), edgeList.end());

		ans = 0;
		UF.initialise(V+5);
		for (int j = 0; j < edgeList.size(); j++)
		{
		    int u, v, w; tie(w, u, v) = edgeList[j];
		    if (!UF.isSameSet(u, v))
            {
                ans += w;
                UF.unionSet(u, v);
            }
		}
		printf("%d\n", ans);
	}
	return 0;
}

/*
6
4 0 4
0 1 2
1 3 9
3 5 1
3 2 5
2
4 0 3 5 2
0 4 1 3 5
*/

Compilation message

roadsideadverts.cpp: In function 'int main()':
roadsideadverts.cpp:164:8: warning: unused variable 'cnt' [-Wunused-variable]
  164 |    int cnt = 0;
      |        ^~~
roadsideadverts.cpp:178:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |   for (int j = 0; j < vertices.size(); j++) {
      |                   ~~^~~~~~~~~~~~~~~~~
roadsideadverts.cpp:179:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  179 |    for (int k = j + 1; k < vertices.size(); k++) {
      |                        ~~^~~~~~~~~~~~~~~~~
roadsideadverts.cpp:197:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |   for (int j = 0; j < edgeList.size(); j++)
      |                   ~~^~~~~~~~~~~~~~~~~
roadsideadverts.cpp:109:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  109 |  scanf("%d", &V);
      |  ~~~~~^~~~~~~~~~
roadsideadverts.cpp:113:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  113 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
roadsideadverts.cpp:146:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  146 |  scanf("%d", &Q);
      |  ~~~~~^~~~~~~~~~
roadsideadverts.cpp:152:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  152 |    scanf("%d", sponsors + j);
      |    ~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 950 ms 10536 KB Output is correct
2 Correct 880 ms 12028 KB Output is correct
3 Correct 908 ms 12024 KB Output is correct
4 Correct 894 ms 11932 KB Output is correct
5 Correct 896 ms 12116 KB Output is correct
6 Correct 962 ms 12064 KB Output is correct
7 Correct 922 ms 12076 KB Output is correct
8 Correct 953 ms 11988 KB Output is correct
9 Correct 936 ms 12100 KB Output is correct
10 Correct 924 ms 12112 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 8780 KB Output is correct
2 Correct 48 ms 11132 KB Output is correct
3 Correct 57 ms 11072 KB Output is correct
4 Correct 42 ms 11172 KB Output is correct
5 Correct 43 ms 11064 KB Output is correct
6 Correct 43 ms 11136 KB Output is correct
7 Correct 46 ms 11104 KB Output is correct
8 Correct 51 ms 11204 KB Output is correct
9 Correct 61 ms 11080 KB Output is correct
10 Correct 43 ms 11188 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5324 KB Output is correct
2 Correct 950 ms 10536 KB Output is correct
3 Correct 880 ms 12028 KB Output is correct
4 Correct 908 ms 12024 KB Output is correct
5 Correct 894 ms 11932 KB Output is correct
6 Correct 896 ms 12116 KB Output is correct
7 Correct 962 ms 12064 KB Output is correct
8 Correct 922 ms 12076 KB Output is correct
9 Correct 953 ms 11988 KB Output is correct
10 Correct 936 ms 12100 KB Output is correct
11 Correct 924 ms 12112 KB Output is correct
12 Correct 39 ms 8780 KB Output is correct
13 Correct 48 ms 11132 KB Output is correct
14 Correct 57 ms 11072 KB Output is correct
15 Correct 42 ms 11172 KB Output is correct
16 Correct 43 ms 11064 KB Output is correct
17 Correct 43 ms 11136 KB Output is correct
18 Correct 46 ms 11104 KB Output is correct
19 Correct 51 ms 11204 KB Output is correct
20 Correct 61 ms 11080 KB Output is correct
21 Correct 43 ms 11188 KB Output is correct
22 Correct 949 ms 10724 KB Output is correct
23 Correct 990 ms 9532 KB Output is correct
24 Execution timed out 1087 ms 11452 KB Time limit exceeded
25 Halted 0 ms 0 KB -