Submission #561599

#	Time	Username	Problem	Language	Result	Execution time	Memory
561599		kingfran1907	Izlet (COI19_izlet)	C++14	100 / 100	956 ms	63400 KiB

izlet

#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 3010;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n;
int niz[maxn][maxn];
int bio[maxn];
vector< vector< int > > v;
vector< int > s;
int parr[maxn];
int sol[maxn];
vector< int > graph[maxn];
vector< pair<int, int> > vs;
bool conn[maxn][maxn];
int dis[maxn];
queue< int > q;

void add(int x, int y) {
	graph[x].push_back(y);
	graph[y].push_back(x);
	vs.push_back(make_pair(x, y));
}

int main() {
	int ran;
	scanf("%d%d", &ran, &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) 
			scanf("%d", &niz[i][j]);
	
	for (int i = 0; i < n; i++) {
		if (bio[i]) continue;
		bio[i] = 1;
		
		vector< int > tren;
		tren.push_back(i);
		for (int j = 0; j < n; j++) {
			if (bio[j] == 0 && niz[i][j] == 1) tren.push_back(j);
		}
		
		for (int j = 0; j < tren.size(); j++) {
			int ac = tren[j];
			//parr[ac] = i;
			bio[ac] = 1;
		}
		v.push_back(tren);
		s.push_back(i);
	}
	
	//for (int i = 0; i < s.size(); i++) printf("%d ", s[i]); printf("\n");
	
	for (int i = 0; i < v.size(); i++) {
		vector< int > &tren = v[i];
		int pt = s[i];
		for (int j = 0; j < tren.size(); j++) {
			int ac = tren[j];
			if (ac != pt) add(pt, ac);
		}
	}
	
	memset(conn, false, sizeof conn);
	for (int i = 0; i < s.size(); i++) {
		for (int j = i + 1; j < s.size(); j++) {
			int a = s[i];
			int b = s[j];
			if (conn[a][b] || niz[a][b] != 2) continue;
			
			vector< int > tren;
			tren.push_back(a);
			tren.push_back(b);
			
			for (int k = j + 1; k < s.size(); k++) {
				int c = s[k];
				if (niz[a][c] == 2 && niz[b][c] == 2) {
					tren.push_back(c);
				}
			}
			
			//printf("found: ");
			//for (int k = 0; k < tren.size(); k++) {
			//	printf("%d ", tren[k]);
			//}
			//printf("\n");
			
			//assert(a == tren[0]);
			for (int k = 1; k < tren.size(); k++) add(tren[0], tren[k]);
			for (int k = 0; k < tren.size(); k++) {
				int x = tren[k];
				for (int l = k + 1; l < tren.size(); l++) {
					int y = tren[l];
					conn[x][y] = conn[y][x] = true;
				}
			}
		}
	}
	
	int nx = 1;
	memset(parr, 0, sizeof parr);
	parr[0] = -1;
	sol[0] = nx++;
	q.push(0);
	
	while(!q.empty()) {
		int x = q.front();
		q.pop();
		for (int i = 0; i < graph[x].size(); i++) {
			int tren = graph[x][i];
			if (sol[tren] != 0) continue;
			dis[tren] = dis[x] + 1;
			parr[tren] = x;
			
			int ac = x;
			while (ac != -1 && niz[ac][tren] != niz[ac][x]) {
				ac = parr[ac];
			}
			
			if (ac != -1) sol[tren] = sol[ac];
			else {
				int mini = inf;
				for (int j = 0; j < n; j++) {
					if (sol[j] > 0 && niz[j][x] == niz[j][tren] && dis[j] < mini) {
						mini = dis[j];
						sol[tren] = sol[j];
					}
				}
			}
			if (sol[tren] == 0) sol[tren] = nx++;
			q.push(tren);
		}
	}
	
	//assert(vs.size() == n - 1);
	for (int i = 0; i < n; i++) printf("%d ", sol[i]); printf("\n");
	for (int i = 0; i < vs.size(); i++) {
		printf("%d %d\n", vs[i].X + 1, vs[i].Y + 1);
	}
	return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'int main()':
izlet.cpp:52:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for (int j = 0; j < tren.size(); j++) {
      |                   ~~^~~~~~~~~~~~~
izlet.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for (int i = 0; i < v.size(); i++) {
      |                  ~~^~~~~~~~~~
izlet.cpp:66:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for (int j = 0; j < tren.size(); j++) {
      |                   ~~^~~~~~~~~~~~~
izlet.cpp:73:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for (int i = 0; i < s.size(); i++) {
      |                  ~~^~~~~~~~~~
izlet.cpp:74:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |   for (int j = i + 1; j < s.size(); j++) {
      |                       ~~^~~~~~~~~~
izlet.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |    for (int k = j + 1; k < s.size(); k++) {
      |                        ~~^~~~~~~~~~
izlet.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |    for (int k = 1; k < tren.size(); k++) add(tren[0], tren[k]);
      |                    ~~^~~~~~~~~~~~~
izlet.cpp:98:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |    for (int k = 0; k < tren.size(); k++) {
      |                    ~~^~~~~~~~~~~~~
izlet.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int l = k + 1; l < tren.size(); l++) {
      |                         ~~^~~~~~~~~~~~~
izlet.cpp:117:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |   for (int i = 0; i < graph[x].size(); i++) {
      |                   ~~^~~~~~~~~~~~~~~~~
izlet.cpp:144:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  144 |  for (int i = 0; i < n; i++) printf("%d ", sol[i]); printf("\n");
      |  ^~~
izlet.cpp:144:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  144 |  for (int i = 0; i < n; i++) printf("%d ", sol[i]); printf("\n");
      |                                                     ^~~~~~
izlet.cpp:145:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  145 |  for (int i = 0; i < vs.size(); i++) {
      |                  ~~^~~~~~~~~~~
izlet.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d%d", &ran, &n);
      |  ~~~~~^~~~~~~~~~~~~~~~~~
izlet.cpp:40:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |    scanf("%d", &niz[i][j]);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57