oj.uz

Submission #155207

# Submission time Handle Problem Language Result Execution time Memory
155207 2019-09-27T06:33:42 Z stefdasca Izlet (COI19_izlet) C++14
100 / 100
 921 ms 74668 KB 
#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 st, int nod, int p)
{
    if(cnt[color[nod]] == 0 && dist[st][nod] == dist[st][p])
        color[st] = color[nod];
    if(p != -1)
        cnt[color[nod]]++;
    for(int i=0; i<v[nod].size(); i++)
    {
        int to = v[nod][i];
        if(viz[to] == false || to == p)
            continue;
        give_color(st, to, 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:35:19: 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:52: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:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < noduri.size(); ++i)
                    ~~^~~~~~~~~~~~~~~
izlet.cpp:82: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 711 ms 36632 KB Output is correct
3 Correct 700 ms 36612 KB Output is correct
4 Correct 683 ms 36472 KB Output is correct
5 Correct 722 ms 36544 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 681 ms 37272 KB Output is correct
2 Correct 697 ms 53568 KB Output is correct
3 Correct 894 ms 73964 KB Output is correct
4 Correct 921 ms 74668 KB Output is correct
5 Correct 675 ms 53668 KB Output is correct
6 Correct 771 ms 60528 KB Output is correct
7 Correct 563 ms 49404 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 711 ms 36632 KB Output is correct
3 Correct 700 ms 36612 KB Output is correct
4 Correct 683 ms 36472 KB Output is correct
5 Correct 722 ms 36544 KB Output is correct
6 Correct 681 ms 37272 KB Output is correct
7 Correct 697 ms 53568 KB Output is correct
8 Correct 894 ms 73964 KB Output is correct
9 Correct 921 ms 74668 KB Output is correct
10 Correct 675 ms 53668 KB Output is correct
11 Correct 771 ms 60528 KB Output is correct
12 Correct 563 ms 49404 KB Output is correct
13 Correct 774 ms 54308 KB Output is correct
14 Correct 844 ms 61432 KB Output is correct
15 Correct 719 ms 53500 KB Output is correct
16 Correct 826 ms 57976 KB Output is correct
17 Correct 835 ms 59948 KB Output is correct
18 Correct 686 ms 53572 KB Output is correct
19 Correct 714 ms 53496 KB Output is correct
20 Correct 703 ms 53580 KB Output is correct
21 Correct 724 ms 54136 KB Output is correct
22 Correct 711 ms 53740 KB Output is correct
23 Correct 781 ms 54508 KB Output is correct
24 Correct 816 ms 60712 KB Output is correct
25 Correct 707 ms 53644 KB Output is correct