oj.uz

Submission #219205

# Submission time Handle Problem Language Result Execution time Memory
219205 2020-04-04T14:13:00 Z dolphingarlic Izlet (COI19_izlet) C++14
100 / 100
 755 ms 88636 KB 
#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.0 / 18.0

# Verdict Execution time Memory 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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory 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

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory 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