oj.uz

Submission #144200

# Submission time Handle Problem Language Result Execution time Memory
144200 2019-08-16T09:55:53 Z LeMur Izlet (COI19_izlet) C++14
100 / 100
 1045 ms 61520 KB 
////////////////////////////////////////////    _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

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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 924 ms 35960 KB Output is correct
3 Correct 912 ms 36040 KB Output is correct
4 Correct 887 ms 36000 KB Output is correct
5 Correct 894 ms 35952 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 881 ms 36132 KB Output is correct
2 Correct 906 ms 36052 KB Output is correct
3 Correct 1037 ms 36352 KB Output is correct
4 Correct 1045 ms 36288 KB Output is correct
5 Correct 878 ms 36092 KB Output is correct
6 Correct 920 ms 35968 KB Output is correct
7 Correct 659 ms 30600 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 508 KB Output is correct
2 Correct 924 ms 35960 KB Output is correct
3 Correct 912 ms 36040 KB Output is correct
4 Correct 887 ms 36000 KB Output is correct
5 Correct 894 ms 35952 KB Output is correct
6 Correct 881 ms 36132 KB Output is correct
7 Correct 906 ms 36052 KB Output is correct
8 Correct 1037 ms 36352 KB Output is correct
9 Correct 1045 ms 36288 KB Output is correct
10 Correct 878 ms 36092 KB Output is correct
11 Correct 920 ms 35968 KB Output is correct
12 Correct 659 ms 30600 KB Output is correct
13 Correct 951 ms 36168 KB Output is correct
14 Correct 998 ms 61520 KB Output is correct
15 Correct 898 ms 53496 KB Output is correct
16 Correct 989 ms 58156 KB Output is correct
17 Correct 1014 ms 59944 KB Output is correct
18 Correct 885 ms 53492 KB Output is correct
19 Correct 899 ms 53580 KB Output is correct
20 Correct 904 ms 53508 KB Output is correct
21 Correct 904 ms 54136 KB Output is correct
22 Correct 916 ms 54008 KB Output is correct
23 Correct 958 ms 54392 KB Output is correct
24 Correct 1004 ms 60668 KB Output is correct
25 Correct 901 ms 53752 KB Output is correct