oj.uz

Submission #144190

# Submission time Handle Problem Language Result Execution time Memory
144190 2019-08-16T09:48:42 Z LeMur Izlet (COI19_izlet) C++14
43 / 100
 1126 ms 36444 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){
    a = findher(a);
    b = findher(b);

    if(a == b)return ;

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

    parent[a] = b;
}

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 504 KB Output is correct
2 Correct 913 ms 36216 KB Output is correct
3 Correct 916 ms 36444 KB Output is correct
4 Correct 893 ms 36216 KB Output is correct
5 Correct 905 ms 36156 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 876 ms 36288 KB Output is correct
2 Correct 896 ms 36216 KB Output is correct
3 Correct 1126 ms 36384 KB Output is correct
4 Correct 1049 ms 36420 KB Output is correct
5 Correct 879 ms 36060 KB Output is correct
6 Correct 907 ms 36344 KB Output is correct
7 Correct 656 ms 30712 KB Output is correct

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 913 ms 36216 KB Output is correct
3 Correct 916 ms 36444 KB Output is correct
4 Correct 893 ms 36216 KB Output is correct
5 Correct 905 ms 36156 KB Output is correct
6 Correct 876 ms 36288 KB Output is correct
7 Correct 896 ms 36216 KB Output is correct
8 Correct 1126 ms 36384 KB Output is correct
9 Correct 1049 ms 36420 KB Output is correct
10 Correct 879 ms 36060 KB Output is correct
11 Correct 907 ms 36344 KB Output is correct
12 Correct 656 ms 30712 KB Output is correct
13 Incorrect 939 ms 35988 KB Output isn't correct
14 Halted 0 ms 0 KB -