Submission #219205

#	Time	Username	Problem	Language	Result	Execution time	Memory
219205		dolphingarlic	Izlet (COI19_izlet)	C++14	100 / 100	755 ms	88636 KiB

izlet

#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;}

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