#include <bits/stdc++.h>
#define FOR(i,x,y) for(int i=x;i < y;i++)
using namespace std;int k,n,a[3001][3001],D[3001][3001];int F[3001],c=1,e=1;bool B[3001];vector<int> C;pair<int,int> A[3001];void E(int N=1){B[N]=true;C.push_back(N);FOR(i,1,n+1)if(!B[i]&&a[N][i]==1){B[i]=true;F[i]=F[N];for(int j:C)D[i][j]=D[j][i]=D[N][j]+1;A[e++]={N,i};}FOR(i,1,n+1)if(!B[i]&&a[N][i]==2){int M=0;for(int j:C){D[i][j]=D[j][i]=D[N][j]+1;if(a[i][j]==a[N][j]&&(!M||D[i][j] < D[i][M]))M=j;}if(M)F[i]=F[M];else F[i]=++c;A[e++]={N,i};E(i);}}int main(){ios_base::sync_with_stdio(0);cin.tie(0);cin>>k>>n;FOR(i,1,n+1)FOR(j,1,n+1)cin>>a[i][j];F[1]=1;E();FOR(i,1,n+1)cout<<F[i]<<" \n"[i==n];FOR(i,1,n)cout<<A[i].first<<' '<<A[i].second<<'\n';return 0;}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
611 ms |
71288 KB |
Output is correct |
| 3 |
Correct |
558 ms |
71160 KB |
Output is correct |
| 4 |
Correct |
563 ms |
58488 KB |
Output is correct |
| 5 |
Correct |
490 ms |
64760 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
513 ms |
69420 KB |
Output is correct |
| 2 |
Correct |
535 ms |
67264 KB |
Output is correct |
| 3 |
Correct |
698 ms |
71544 KB |
Output is correct |
| 4 |
Correct |
755 ms |
75896 KB |
Output is correct |
| 5 |
Correct |
517 ms |
82040 KB |
Output is correct |
| 6 |
Correct |
609 ms |
70780 KB |
Output is correct |
| 7 |
Correct |
443 ms |
58800 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
5 ms |
640 KB |
Output is correct |
| 2 |
Correct |
611 ms |
71288 KB |
Output is correct |
| 3 |
Correct |
558 ms |
71160 KB |
Output is correct |
| 4 |
Correct |
563 ms |
58488 KB |
Output is correct |
| 5 |
Correct |
490 ms |
64760 KB |
Output is correct |
| 6 |
Correct |
513 ms |
69420 KB |
Output is correct |
| 7 |
Correct |
535 ms |
67264 KB |
Output is correct |
| 8 |
Correct |
698 ms |
71544 KB |
Output is correct |
| 9 |
Correct |
755 ms |
75896 KB |
Output is correct |
| 10 |
Correct |
517 ms |
82040 KB |
Output is correct |
| 11 |
Correct |
609 ms |
70780 KB |
Output is correct |
| 12 |
Correct |
443 ms |
58800 KB |
Output is correct |
| 13 |
Correct |
668 ms |
79864 KB |
Output is correct |
| 14 |
Correct |
656 ms |
74140 KB |
Output is correct |
| 15 |
Correct |
564 ms |
87416 KB |
Output is correct |
| 16 |
Correct |
635 ms |
72696 KB |
Output is correct |
| 17 |
Correct |
596 ms |
67448 KB |
Output is correct |
| 18 |
Correct |
682 ms |
88636 KB |
Output is correct |
| 19 |
Correct |
584 ms |
82648 KB |
Output is correct |
| 20 |
Correct |
545 ms |
87224 KB |
Output is correct |
| 21 |
Correct |
621 ms |
75128 KB |
Output is correct |
| 22 |
Correct |
616 ms |
88404 KB |
Output is correct |
| 23 |
Correct |
607 ms |
73848 KB |
Output is correct |
| 24 |
Correct |
660 ms |
73848 KB |
Output is correct |
| 25 |
Correct |
580 ms |
88244 KB |
Output is correct |
