oj.uz

Submission #155208

# Submission time Handle Problem Language Result Execution time Memory
155208 2019-09-27T06:36:38 Z stefdasca Izlet (COI19_izlet) C++14
100 / 100
 888 ms 51448 KB 
/*
    editorial = https://codeforces.com/blog/entry/66506?#comment-505659
*/
#include<bits/stdc++.h>
using namespace std;
int subtask, n, dist[3002][3002];
int nr;
pair<int, int> ans[3002];
vector<int>v[3002];
int tt[3002], color[3002];
int Find(int nod)
{
    if(tt[nod] == nod)
        return nod;
    return tt[nod] = Find(tt[nod]);
}
void Union(int a, int b)
{
    if(Find(a) == Find(b))
        return;
    ans[++nr] = {a, b};
    v[a].push_back(b);
    v[b].push_back(a);
    a = Find(a);
    b = Find(b);
    tt[a] = b;
}

int cnt[3002], viz[3002];
int newcolor = 0;

void give_color(int grupa, int nod, int p)
{
    if(cnt[color[nod]] == 0 && dist[grupa][nod] == dist[grupa][p])
        color[grupa] = color[nod];
    if(p != -1)
        cnt[color[nod]]++;
    for(int i = 0; i < v[nod].size(); i++)
    {
        int vecin = v[nod][i];
        if(viz[vecin] == 0 || vecin == p)
            continue;
        give_color(grupa, vecin, nod);
    }
    if(p != -1)
        cnt[color[nod]]--;
}

void dfs(int nod, int dad)
{
    viz[nod] = 1;
    give_color(nod, nod, -1);
    if(color[nod] == 0)
        color[nod] = ++newcolor;
    for(int i = 0; i < v[nod].size(); i++)
    {
        int vecin = v[nod][i];
        if(vecin == dad)
            continue;
        dfs(vecin, nod);
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> subtask;
    cin >> n;
    for(int i = 1; i <= n; ++i)
        tt[i] = i;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            cin >> dist[i][j];
            if(dist[i][j] == 1)
                Union(i, j);
        }
    vector<int>noduri;
    for(int i = 1; i <= n; ++i)
        if(Find(i) == i)
            noduri.push_back(i);
    for(int i = 0; i < noduri.size(); ++i)
    {
        int nod = noduri[i];
        for(int j = i+1; j < noduri.size(); ++j)
        {
            int vecin = noduri[j];
            if(dist[nod][vecin] == 2)
                Union(nod, vecin);
        }
    }
    cnt[0] = 1;
    dfs(1, 0);
    for(int i = 1; i <= n; ++i)
        cout << color[i] << " ";
    cout << '\n';
    for(int i = 1; i < n; ++i)
        cout << ans[i].first << " " << ans[i].second << '\n';
    return 0;
}

Compilation message

izlet.cpp: In function 'void give_color(int, int, int)':
izlet.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); i++)
                    ~~^~~~~~~~~~~~~~~
izlet.cpp: In function 'void dfs(int, int)':
izlet.cpp:55:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); i++)
                    ~~^~~~~~~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:82:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < noduri.size(); ++i)
                    ~~^~~~~~~~~~~~~~~
izlet.cpp:85:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = i+1; j < noduri.size(); ++j)
                          ~~^~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 704 ms 37128 KB Output is correct
3 Correct 719 ms 37108 KB Output is correct
4 Correct 705 ms 37116 KB Output is correct
5 Correct 708 ms 36208 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 36056 KB Output is correct
2 Correct 711 ms 36072 KB Output is correct
3 Correct 885 ms 36160 KB Output is correct
4 Correct 888 ms 36228 KB Output is correct
5 Correct 676 ms 35888 KB Output is correct
6 Correct 752 ms 35896 KB Output is correct
7 Correct 552 ms 30584 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 704 ms 37128 KB Output is correct
3 Correct 719 ms 37108 KB Output is correct
4 Correct 705 ms 37116 KB Output is correct
5 Correct 708 ms 36208 KB Output is correct
6 Correct 683 ms 36056 KB Output is correct
7 Correct 711 ms 36072 KB Output is correct
8 Correct 885 ms 36160 KB Output is correct
9 Correct 888 ms 36228 KB Output is correct
10 Correct 676 ms 35888 KB Output is correct
11 Correct 752 ms 35896 KB Output is correct
12 Correct 552 ms 30584 KB Output is correct
13 Correct 825 ms 35960 KB Output is correct
14 Correct 862 ms 35900 KB Output is correct
15 Correct 694 ms 35896 KB Output is correct
16 Correct 798 ms 35900 KB Output is correct
17 Correct 813 ms 36008 KB Output is correct
18 Correct 714 ms 36052 KB Output is correct
19 Correct 703 ms 35888 KB Output is correct
20 Correct 705 ms 37832 KB Output is correct
21 Correct 721 ms 42856 KB Output is correct
22 Correct 717 ms 46780 KB Output is correct
23 Correct 765 ms 48828 KB Output is correct
24 Correct 808 ms 51448 KB Output is correct
25 Correct 725 ms 50712 KB Output is correct