Submission #245482

#	Time	Username	Problem	Language	Result	Execution time	Memory
245482		mhy908	Izlet (COI19_izlet)	C++14	0 / 100	927 ms	72216 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;
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]){
            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){
                if(arr[i][j]==arr[num][j]){
                    assert(tmp==0||col[j]==tmp);
                    tmp=col[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 (stderr)

izlet.cpp: In function 'int main()':
izlet.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%*d %d", &n);
     ~~~~~^~~~~~~~~~~~~~
izlet.cpp:44: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
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57