Submission #144200

#	Time	Username	Problem	Language	Result	Execution time	Memory
144200		LeMur	Izlet (COI19_izlet)	C++14	100 / 100	1045 ms	61520 KiB

izlet

////////////////////////////////////////////    _LeMur_
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#define _CRT_SECURE_NO_WARNINGS
#include <unordered_map>
#include <unordered_set>
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cassert>
#include <chrono>
#include <random>
#include <bitset>
#include <cstdio>
#include <vector>
#include <string>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <list>
#include <map>
#include <set>

using namespace std;

const int N = 3005;
const int inf = 1000 * 1000 * 1000;
const int mod = 1000 * 1000 * 1000 + 7;

int t;
int n;
int a[N][N];

int parent[N] , cnt[N];

int answ[N];
vector < pair<int,int> > edge;
vector <int> g[N];

int findher(int v){
    if(v == parent[v])return v;
    return parent[v] = findher(parent[v]);
}

void tmerge(int a,int b){
    int aa = findher(a);
    int bb = findher(b);

    if(aa == bb)return ;

    edge.push_back(make_pair(a , b));
    g[a].push_back(b);
    g[b].push_back(a);

    parent[aa] = bb;
}

bool used[N];
int timer = 0;

void give_color(int st,int v,int p){
    if(cnt[ answ[v] ] == 0){
        if(a[st][v] == a[st][p]){
            answ[st] = answ[v];
        }
    }

    if(p != -1) cnt[ answ[v] ]++;

    for(int i=0;i<(int)g[v].size();i++){
        int to = g[v][i];
        if(used[to] == false || to == p)continue;
        give_color(st , to , v);
    }

    if(p != -1) cnt[ answ[v] ]--;
}

void dfs(int v,int p){
    used[v] = true;
    give_color(v , v , -1);

    if(answ[v] == 0) answ[v] = ++timer;

    for(int i=0;i<(int)g[v].size();i++){
        int to = g[v][i];
        if(to == p)continue;
        dfs(to , v);
    }
}

int main(){
	mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
    cin >> t;
    cin >> n;
    for(int i=1;i<=n;i++){
        parent[i] = i;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            scanf("%d",&a[i][j]);
            if(i == j)continue;
            if(a[i][j] == 1){
                tmerge(i , j);
            }
        }
    }
    vector <int> vert;
    for(int i=1;i<=n;i++){
        vert.push_back(findher(i));
    }
    sort(vert.begin() , vert.end());
    vert.resize( unique(vert.begin() , vert.end()) - vert.begin() );
    for(int i=0;i<(int)vert.size();i++){
        int v1 = vert[i];
        for(int j=i + 1;j<(int)vert.size();j++){
            int v2 = vert[j];
            if(a[v1][v2] == 2){
                tmerge(v1 , v2);
            }
        }
    }

    cnt[0] = 1;
    dfs(1 , 0);

    for(int i=1;i<=n;i++){
        cout << answ[i] << " ";
    }
    cout << endl;
    for(int i=0;i<n-1;i++){
        cout << edge[i].first << " " << edge[i].second << endl;
    }
    return 0;
}
/*
2
4
1 2 2 2
2 1 2 2
2 2 1 2
2 2 2 1
*/

Compilation message (stderr)

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

• Subtask 1: 18 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57