oj.uz

Submission #245488

# Submission time Handle Problem Language Result Execution time Memory
245488 2020-07-06T14:13:16 Z mhy908 Izlet (COI19_izlet) C++14
0 / 100
 1042 ms 69860 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef pair<int, int> pii;

int n;
int arr[3010][3010], col[3010], c, d[3010][3010];
vector<int> vc;
vector<pii> ed;

void dfs(int num){
    vc.eb(num);
    for(int i=1; i<=n; i++){
        if(i==num)continue;
        if(arr[num][i]==1&&!col[i]){
            for(auto j:vc){
                d[i][j]=d[num][j]+1;
                d[j][i]=d[num][j]+1;
            }
            col[i]=col[num];
            ed.eb(i, num);
        }
    }
    for(int i=1; i<=n; i++){
        if(arr[num][i]==2&&!col[i]){
            int tmp=0;
            for(auto j:vc){
                d[i][j]=d[num][j]+1;
                d[j][i]=d[num][j]+1;
            }
            for(auto j:vc){
                if(arr[i][j]==arr[num][j]){
                    if(!tmp)tmp=j;
                    else if(d[i][tmp]>d[i][j])tmp=j;
                }
            }
            if(tmp)col[i]=tmp;
            else col[i]=++c;
            ed.eb(i, num);
            dfs(i);
        }
    }
}

int main(){
    scanf("%*d %d", &n);
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            scanf("%d", &arr[i][j]);
        }
    }
    col[1]=++c;
    dfs(1);
    for(int i=1; i<=n; i++)printf("%d ", col[i]);
    puts("");
    for(auto i:ed)printf("%d %d\n", i.F, i.S);
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:49:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%*d %d", &n);
     ~~~~~^~~~~~~~~~~~~~
izlet.cpp:52:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &arr[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1042 ms 69860 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -