oj.uz

Submission #219204

# Submission time Handle Problem Language Result Execution time Memory
219204 2020-04-04T14:11:46 Z dolphingarlic Izlet (COI19_izlet) C++14
18 / 100
 2000 ms 88928 KB 
#include <bits/stdc++.h>
#define FOR(i,x,y) for(int i=x;i < y;i++)
int k,n,a[3001][3001],D[3001][3001];int F[3001],c=1,e=1;bool B[3001];std::vector<int> C;std::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(){std::cin>>k>>n;FOR(i,1,n+1)FOR(j,1,n+1)std::cin>>a[i][j];F[1]=1;E();FOR(i,1,n+1)std::cout<<F[i]<<" \n"[i==n];FOR(i,1,n)std::cout<<A[i].first<<' '<<A[i].second<<'\n';return 0;}

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 1916 ms 88928 KB Output is correct
3 Correct 1874 ms 88696 KB Output is correct
4 Correct 1857 ms 76136 KB Output is correct
5 Correct 1933 ms 82188 KB Output is correct

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1897 ms 87160 KB Output is correct
2 Correct 1836 ms 84732 KB Output is correct
3 Execution timed out 2079 ms 30128 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 1916 ms 88928 KB Output is correct
3 Correct 1874 ms 88696 KB Output is correct
4 Correct 1857 ms 76136 KB Output is correct
5 Correct 1933 ms 82188 KB Output is correct
6 Correct 1897 ms 87160 KB Output is correct
7 Correct 1836 ms 84732 KB Output is correct
8 Execution timed out 2079 ms 30128 KB Time limit exceeded
9 Halted 0 ms 0 KB -