Submission #312752

#	Time	Username	Problem	Language	Result	Execution time	Memory
312752		galca	Pastiri (COI20_pastiri)	C++14	0 / 100	1097 ms	86424 KiB

pastiri

#include <iostream>
#include <vector>
#include <set>
#include <list>

using namespace std;

typedef struct node {
	bool hasSheep;
	int id;
	vector<int> connected;
	set<int> closestSheeps;
	int d;
	int myShepperd;
	int myShepperdD;
} Node;

typedef struct token {
	int src;
	int lastVisited;
	int at;
	int d;
} Token;

int main() {
	int n, k;

	cin >> n >> k;

	vector<Node> tree(n);

	for (int i = 0; i < n; i++) {
		Node n;
		n.id = i;
		n.d = 0;
		n.hasSheep = false;
		tree[i] = n;
	}

	for (int i = 0; i < n - 1; i++) {
		int a, b;
		cin >> a >> b;
		tree[a - 1].connected.push_back(b - 1);
		tree[b - 1].connected.push_back(a - 1);
	}

	set<int> shepperds;
	list<Token> tokens;

	for (int i = 0; i < k; i++) {
		int id;
		cin >> id;
		tree[id - 1].hasSheep = true;
		tree[id - 1].myShepperd = id - 1;
		tree[id - 1].myShepperdD = 0;
		Token t;
		t.src = id - 1;
		t.at = id - 1;
		t.lastVisited = -1;
		t.d = 0;
		tokens.push_back(t);
	}

	while (tokens.size() > 0) {
		int iter = 0;
		Token t = tokens.front();

		tokens.pop_front();

			Node& n = tree[t.at];
			Node& s = tree[t.src];
			if (s.myShepperdD < t.d) {
				s.myShepperdD = t.d;
				s.myShepperd = t.at;
			}
			t.d++;

			for (int i = 0; i < n.connected.size(); i++) {
				int id = n.connected[i];
				if (id == t.lastVisited) {
					continue;
				}
				Node& next = tree[id];
				if ((next.closestSheeps.size() != 0) && (next.d < t.d)) {
					continue;
				}
				if (next.hasSheep) {
					continue;
				}
				next.d = t.d;
				next.closestSheeps.insert(t.src);
				Token tn = t;
				tn.at = id;
				tn.lastVisited = t.at;
				tokens.push_back(tn);
			}			
	}

	for (int i = 0; i < n; i++) {
		Node cn = tree[i];
		if (cn.hasSheep) {
			shepperds.insert(cn.myShepperd);
		}
	}
	cout << shepperds.size() << endl;
	set<int>::iterator itr;
	for (itr = shepperds.begin(); itr != shepperds.end(); itr++) {
		cout << *itr+1 << " ";
	}
	cout << endl; 

	return 0;
}

Compilation message (stderr)

pastiri.cpp: In function 'int main()':
pastiri.cpp:78:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for (int i = 0; i < n.connected.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~
pastiri.cpp:65:7: warning: unused variable 'iter' [-Wunused-variable]
   65 |   int iter = 0;
      |       ^~~~

• Subtask 1: 0 / 8
• Subtask 2: 0 / 18
• Subtask 3: 0 / 23
• Subtask 4: 0 / 51