oj.uz

Submission #245674

# Submission time Handle Problem Language Result Execution time Memory
245674 2020-07-07T05:55:32 Z dennisstar Izlet (COI19_izlet) C++17
43 / 100
 932 ms 75512 KB 
#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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 712 ms 58124 KB Output is correct
3 Correct 694 ms 58232 KB Output is correct
4 Correct 571 ms 50936 KB Output is correct
5 Correct 645 ms 55160 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 55672 KB Output is correct
2 Correct 602 ms 52476 KB Output is correct
3 Correct 932 ms 70724 KB Output is correct
4 Correct 897 ms 75512 KB Output is correct
5 Correct 552 ms 49912 KB Output is correct
6 Correct 661 ms 44280 KB Output is correct
7 Correct 490 ms 38136 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 712 ms 58124 KB Output is correct
3 Correct 694 ms 58232 KB Output is correct
4 Correct 571 ms 50936 KB Output is correct
5 Correct 645 ms 55160 KB Output is correct
6 Correct 689 ms 55672 KB Output is correct
7 Correct 602 ms 52476 KB Output is correct
8 Correct 932 ms 70724 KB Output is correct
9 Correct 897 ms 75512 KB Output is correct
10 Correct 552 ms 49912 KB Output is correct
11 Correct 661 ms 44280 KB Output is correct
12 Correct 490 ms 38136 KB Output is correct
13 Incorrect 753 ms 49148 KB Integer 0 violates the range [1, 3000]
14 Halted 0 ms 0 KB -