| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 144140 |
2019-08-16T07:56:40 Z |
LeMur |
Izlet (COI19_izlet) |
C++14 |
|
847 ms |
72080 KB |
//////////////////////////////////////////// _LeMur_
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <list>
#include <map>
#include <set>
using namespace std;
const int N = 3005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;
int t;
int n;
int a[N][N];
vector <int> g[N];
int answ[N];
vector < pair<int,int> > edge;
int used[N];
int main(){
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
cin >> t;
cin >> n;
int s = 0 , id;
for(int i=1;i<=n;i++){
int mx = 0;
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
mx = max(mx , a[i][j]);
}
if(mx > s){
s = mx;
id = i;
}
}
for(int i=1;i<=n;i++){
g[ a[id][i] ].push_back(i);
answ[i] = a[id][i];
}
for(int i=1;i<=s;i++){
set <int> q;
for(int j=0;j<(int)g[i].size();j++){
q.insert(g[i][j]);
}
int col = 0;
while(!q.empty()){
++col;
int v = *q.begin();
q.erase(q.begin());
bool T = false;
while(true){
used[v] = col;
bool flag = false;
int go = -1;
for(int h=0;h<(int)g[i].size();h++){
int p = g[i][h];
if(used[p])continue;
if(v == p || a[v][p] != 1)continue;
if(q.find(p) == q.end()){
edge.push_back(make_pair(v , p));
T = true;
break;
}
go = p;
}
if(T)break;
if(!flag){
for(int j=0;j<(int)g[i - 1].size();j++){
int p = g[i - 1][j];
if(a[v][p] == 2){
edge.push_back(make_pair(v , p));
flag = true;
break;
}
}
if(flag == false){
if(i == 1)break;
assert(go != -1);
edge.push_back(make_pair(v , go));
v = go;
q.erase(v);
}
else
break;
}
}
}
}
for(int i=1;i<=n;i++){
cout << answ[i] << " ";
}
cout << endl;
for(int i=0;i<n-1;i++){
cout << edge[i].first << " " << edge[i].second << endl;
}
return 0;
}
/*
2
4
1 2 2 2
2 1 2 2
2 2 1 2
2 2 2 1
*/
Compilation message
izlet.cpp: In function 'int main()':
izlet.cpp:50:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a[i][j]);
~~~~~^~~~~~~~~~~~~~~
izlet.cpp:60:26: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
answ[i] = a[id][i];
~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Integer 0 violates the range [1, 30] |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
847 ms |
72080 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
504 KB |
Integer 0 violates the range [1, 30] |
| 2 |
Halted |
0 ms |
0 KB |
- |
