Submission #245489

#	Time	Username	Problem	Language	Result	Execution time	Memory
245489		mhy908	Izlet (COI19_izlet)	C++14	100 / 100	1171 ms	97052 KiB

izlet

#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]=col[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 (stderr)

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: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57