Submission #245674

#	Time	Username	Problem	Language	Result	Execution time	Memory
245674		dennisstar	Izlet (COI19_izlet)	C++17	43 / 100	932 ms	75512 KiB

izlet

#include <bits/stdc++.h>
#define eb emplace_back
using namespace std;

const int MX = 3e3 + 5;

int pr[MX], clr[MX];
int gp(int n) { return pr[n]?(pr[n]=gp(pr[n])):n; }
void un(int x, int y) {
	x=gp(x), y=gp(y);
	if (x!=y) pr[y]=x;
}

int T, N, mt[MX][MX], dst[MX][MX], tp[MX];
vector<int> q[MX];

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>T>>N;
	for (int i=1; i<=N; i++) for (int j=1; j<=N; j++) {
		cin>>mt[i][j];
		if (mt[i][j]==1) un(i, j);
	}
	vector<int> v;
	for (int i=1; i<=N; i++) {
		q[gp(i)].eb(i);
		if (gp(i)==i) v.eb(i);
	}

	for (auto &i:v) for (auto &j:v) dst[i][mt[i][j]]++, tp[i]=max(tp[i], mt[i][j]);
	int mx=0, mi;
	for (int i=0; i<v.size(); i++) if (mx<tp[v[i]]) mx=tp[v[i]], mi=i;
	swap(v[0], v[mi]);
	for (int i=0; i<v.size()-1; i++) {
		mx=0;
		for (int j=i+1; j<v.size(); j++) {
			dst[v[j]][mt[v[i]][v[j]]]--;
			while (dst[v[j]][tp[v[j]]]==0) tp[v[j]]--;
			if (mt[v[i]][v[j]]==2&&mx<tp[v[j]]) mx=tp[v[j]], mi=j;
		}
		swap(v[i+1], v[mi]);
	}

	clr[v[0]]=1;
	vector<int> w(N+1);
	for (int i=1; i<v.size(); i++) {
		if (mt[v[0]][v[i]]!=mt[v[0]][v[i-1]]) { clr[v[i]]=mt[v[0]][v[i]]; continue; }
		fill(w.begin(), w.end(), 0);
		for (int j=i-1; j>=0; j--) {
			if (w[clr[v[j]]]==0&&mt[v[i]][v[j]]==mt[v[i]][v[j+1]]) { clr[v[i]]=clr[v[j]]; break; }
			w[clr[v[j]]]++;
		}
	}

	for (int i=1; i<=N; i++) cout<<clr[gp(i)]<<' ';
	cout<<'\n';
	for (int i=0; i<v.size(); i++) {
		if (i) cout<<q[v[i-1]].back()<<' '<<q[v[i]][0]<<'\n';
		for (int j=1; j<q[v[i]].size(); j++) cout<<q[v[i]][j-1]<<' '<<q[v[i]][j]<<'\n';
	}
	return 0;
}

Compilation message (stderr)

izlet.cpp: In function 'int main()':
izlet.cpp:32:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v.size(); i++) if (mx<tp[v[i]]) mx=tp[v[i]], mi=i;
                ~^~~~~~~~~
izlet.cpp:34:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v.size()-1; i++) {
                ~^~~~~~~~~~~
izlet.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=i+1; j<v.size(); j++) {
                   ~^~~~~~~~~
izlet.cpp:46:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=1; i<v.size(); i++) {
                ~^~~~~~~~~
izlet.cpp:57:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<v.size(); i++) {
                ~^~~~~~~~~
izlet.cpp:59:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=1; j<q[v[i]].size(); j++) cout<<q[v[i]][j-1]<<' '<<q[v[i]][j]<<'\n';
                 ~^~~~~~~~~~~~~~~
izlet.cpp:33:17: warning: 'mi' may be used uninitialized in this function [-Wmaybe-uninitialized]
  swap(v[0], v[mi]);
                 ^

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