oj.uz

Submission #240939

# Submission time Handle Problem Language Result Execution time Memory
240939 2020-06-21T15:57:11 Z brcode Izlet (COI19_izlet) C++14
100 / 100
 731 ms 72568 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXN =5e3+5;
int dist[MAXN][MAXN];
vector<int> v1[MAXN];
int cnt[MAXN];
int col[MAXN];
vector<pair<int,int>> edges;
bool visited[MAXN];
int p[MAXN];
int n;
int nxt;
int sz[MAXN];
void colour(int a,int b,int c){
    if(cnt[col[b]] == 0 && dist[a][b] == dist[a][c]){
        col[a] = col[b];
    }
    if(c!=-1){
        cnt[col[b]]++;
    }
    for(int x:v1[b]){
        if((!visited[x])||x==c){
            continue;
        }
        colour(a,x,b);
    }
    if(c!=-1){
        cnt[col[b]]--;
    }
}
void dfs(int curr,int par){
    visited[curr] = true;
    colour(curr,curr,-1);
    if(col[curr] == 0){
        col[curr] = nxt+1;
        nxt++;
    }
    for(int x:v1[curr]){
        if(!visited[x]){
           
            dfs(x,curr);
        }
    }
}

int findpar(int a){
    if(p[a] == a){
        return a;
    }
    return p[a] = findpar(p[a]);
}
void merge(int a,int b){
    if(findpar(a)==findpar(b)){
        return;
    }
    v1[a].push_back(b);
    v1[b].push_back(a);
    edges.push_back(make_pair(a,b));
    a = findpar(a);
    b=  findpar(b);
    
    if(sz[b]>sz[a]){
        swap(a,b);
    }
    p[b] = a;
    sz[a]+=sz[b];
    
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin>>tc;
    cin>>n;
    for(int i=1;i<=n;i++){
        p[i] = i;
        sz[i] = 1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>dist[i][j];
            if(dist[i][j] == 1){
                merge(i,j);
            }
        }
    }
    vector<int> nodes;
    for(int i=1;i<=n;i++){
        if(p[i] == i){
            nodes.push_back(i);
        }
    }
    for(int i=0;i<nodes.size();i++){
        for(int j=i+1;j<nodes.size();j++){
            if(dist[nodes[i]][nodes[j]] == 2){
                merge(nodes[i],nodes[j]);
            }   
        }
    }
    dfs(1,0);
    for(int i=1;i<=n;i++){
        cout<<col[i]<<" ";
    }
    cout<<'\n';
    for(auto x:edges){
        cout<<x.first<<" "<<x.second<<'\n';
    }
}

Compilation message

izlet.cpp: In function 'int main()':
izlet.cpp:94:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<nodes.size();i++){
                 ~^~~~~~~~~~~~~
izlet.cpp:95:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=i+1;j<nodes.size();j++){
                       ~^~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 607 ms 47992 KB Output is correct
3 Correct 587 ms 47992 KB Output is correct
4 Correct 568 ms 47864 KB Output is correct
5 Correct 613 ms 47864 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 594 ms 48152 KB Output is correct
2 Correct 583 ms 47992 KB Output is correct
3 Correct 721 ms 48452 KB Output is correct
4 Correct 731 ms 56576 KB Output is correct
5 Correct 553 ms 65528 KB Output is correct
6 Correct 602 ms 72568 KB Output is correct
7 Correct 456 ms 49676 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 607 ms 47992 KB Output is correct
3 Correct 587 ms 47992 KB Output is correct
4 Correct 568 ms 47864 KB Output is correct
5 Correct 613 ms 47864 KB Output is correct
6 Correct 594 ms 48152 KB Output is correct
7 Correct 583 ms 47992 KB Output is correct
8 Correct 721 ms 48452 KB Output is correct
9 Correct 731 ms 56576 KB Output is correct
10 Correct 553 ms 65528 KB Output is correct
11 Correct 602 ms 72568 KB Output is correct
12 Correct 456 ms 49676 KB Output is correct
13 Correct 641 ms 66424 KB Output is correct
14 Correct 683 ms 52856 KB Output is correct
15 Correct 641 ms 65580 KB Output is correct
16 Correct 679 ms 52436 KB Output is correct
17 Correct 680 ms 52400 KB Output is correct
18 Correct 608 ms 65504 KB Output is correct
19 Correct 654 ms 65476 KB Output is correct
20 Correct 594 ms 65504 KB Output is correct
21 Correct 657 ms 66144 KB Output is correct
22 Correct 606 ms 65764 KB Output is correct
23 Correct 607 ms 66256 KB Output is correct
24 Correct 663 ms 53496 KB Output is correct
25 Correct 596 ms 65656 KB Output is correct