Submission #517054

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
517054	2022-01-22T12:56:46 Z	aurims	Fire drill (LMIO18_sauga)	C++14	56.9203 / 100	217 ms	4304 KB

sauga

#include <iostream>
#include <vector>
#define debug cout << "alion\n"
#define MAX (int)10e3
#define pb push_back
using namespace std;

/* input with no loops in graph
0 7 1
2 2 3
0
3 4 5 6
0
1 7
0
0
*/

void test_print(vector<vector<int>> l)
{
	for(int i = 0; i < l.size(); i++)
	{
		cout << "City " << i << ".\n";
		for(int j = 0; j < l[i].size(); j++)
			cout << l[i][j] << ' ';
		cout << '\n';
	}
}

void evacuate(vector<vector<int>> &l, int ind, vector<int> &e)
{
	e.pb(ind);
	for(int i = 0; i < l.size(); i++)
	{
		if(i == ind) continue;
		for(int j = 0; j < l[i].size(); j++)
			if(l[i][j] == ind)
				l[i].erase(l[i].begin()+j);
	}
	l[ind] = {-1}; // we can't erase the node from the graph since it would change the numerings
}

int main()
{
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	int T, N, S;
	cin >> T >> N >> S;
	vector<vector<int>> l(N);
	for(int i = 0; i < N; i++)
	{
		int n;
		cin >> n;
		l[i].resize(n);
		for(int j = 0; j < n; j++)
		{
			cin >> l[i][j];
			l[i][j]--;
		}
	}
	vector<int> evac;
	while(evac.size() < N)
	{
		// remove all nodes that have no outgoing edges
		for(int i = 0; i < l.size(); i++)
		{
			if(l[i].empty()) // if node has no outgoing edges
			{
				evacuate(l, i, evac);
				i = -1;
			}
		}
		// remove a node with most outgoing edges
		int mxe = -1;
		int mxind = -1;
		for(int i = 0; i < l.size(); i++)
		{
			if((int)l[i].size() > mxe && l[i][0] != -1)
			{
				mxe = l[i].size();
				mxind = i;
			}
		}
		if(mxind != -1) evacuate(l, mxind, evac);
		//getchar();
	}
	for(const int idx : evac)
		cout << idx+1 << '\n';
}

Compilation message

sauga.cpp: In function 'void test_print(std::vector<std::vector<int> >)':
sauga.cpp:21:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0; i < l.size(); i++)
      |                 ~~^~~~~~~~~~
sauga.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |   for(int j = 0; j < l[i].size(); j++)
      |                  ~~^~~~~~~~~~~~~
sauga.cpp: In function 'void evacuate(std::vector<std::vector<int> >&, int, std::vector<int>&)':
sauga.cpp:33:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(int i = 0; i < l.size(); i++)
      |                 ~~^~~~~~~~~~
sauga.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int j = 0; j < l[i].size(); j++)
      |                  ~~^~~~~~~~~~~~~
sauga.cpp: In function 'int main()':
sauga.cpp:62:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |  while(evac.size() < N)
      |        ~~~~~~~~~~~~^~~
sauga.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for(int i = 0; i < l.size(); i++)
      |                  ~~^~~~~~~~~~
sauga.cpp:76:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   for(int i = 0; i < l.size(); i++)
      |                  ~~^~~~~~~~~~

Subtask #1

56.9203114834 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	206 ms	2944 KB	Output is correct
2	Partially correct	7 ms	332 KB	Output is partially correct
3	Partially correct	7 ms	368 KB	Output is partially correct
4	Partially correct	12 ms	332 KB	Output is partially correct
5	Partially correct	7 ms	388 KB	Output is partially correct
6	Partially correct	8 ms	396 KB	Output is partially correct
7	Partially correct	34 ms	844 KB	Output is partially correct
8	Partially correct	217 ms	4304 KB	Output is partially correct
9	Partially correct	28 ms	716 KB	Output is partially correct
10	Correct	5 ms	332 KB	Output is correct