oj.uz

Submission #117058

# Submission time Handle Problem Language Result Execution time Memory
117058 2019-06-14T14:30:13 Z pavel Izlet (COI19_izlet) C++14
100 / 100
 1032 ms 83272 KB 
#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

const int MAXN = 3003;

int t,n;
int colors[MAXN][MAXN];


bool done[MAXN], d2[MAXN][MAXN];
vector<int> graph[MAXN];
int c[MAXN], par[MAXN], dep[MAXN];


void make_tree(){
    vector<int> ocs;
    for(int i=0;i<n;++i){
        if(!done[i]){
            done[i]=true;
            for(int j=i+1;j<n;++j){
                if(!done[j] && colors[i][j]==1){
                    done[j]=true;
                    graph[i].push_back(j);
                    graph[j].push_back(i);
                }
            }
            ocs.push_back(i);
        }
    }
    for(int i=0;i<ocs.size();++i){
        for(int j=i+1;j<ocs.size();++j){
            if(colors[ocs[i]][ocs[j]]==2 && !d2[ocs[i]][ocs[j]]){
                vector<int> tc;
                tc.push_back(ocs[i]);
                tc.push_back(ocs[j]);
                for(int k=j+1;k<ocs.size();++k){
                    if(colors[ocs[i]][ocs[k]]==2 && colors[ocs[j]][ocs[k]]==2){
                        tc.push_back(ocs[k]);
                    }
                }
                for(int k=0;k<tc.size();++k){
                    if(k){
                        graph[tc[k]].push_back(tc[0]);
                        graph[tc[0]].push_back(tc[k]);
                    }
                    for(int l=0;l<k;++l){
                        d2[tc[k]][tc[l]]=d2[tc[l]][tc[k]]=true;
                    }
                }
            }
        }
    }
}

void color_tree(){
    queue<int> todo;
    todo.push(0);
    par[0]=-1;
    dep[0]=0;
    c[0]=1;
    int nfc=2;
    while(!todo.empty()){
        int curr = todo.front();
        todo.pop();
        for(int i:graph[curr]){
            if(!c[i]){
                par[i]=curr;
                dep[i]=dep[curr]+1;
                int p=curr;
                while(p!=-1 && colors[p][curr]!=colors[p][i]) p=par[p];
                if(p==-1){
                    int d=MAXN;
                    for(int j=0;j<n;++j){
                        if(c[j] && colors[j][i]==colors[j][curr] && d>dep[j]){
                            d=dep[j];
                            c[i]=c[j];
                        }
                    }
                }else{
                    c[i]=c[p];
                }
                if(!c[i]) c[i]=nfc++;
                todo.push(i);
            }
        }

    }
}

int main(){
    scanf("%d%d", &t, &n);
    for(int i=0;i<n;++i)
        for(int j=0;j<n;++j)
            scanf("%d", &colors[i][j]);
    make_tree();
    color_tree();
    for(int i=0;i<n;++i){
        printf("%d ", c[i]);
    }
    puts("");
    for(int i=0;i<n;++i){
        for(auto j:graph[i]){
            if(i<j) printf("%d %d\n", i+1, j+1);
        }
    }
}

Compilation message

izlet.cpp: In function 'void make_tree()':
izlet.cpp:33:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<ocs.size();++i){
                 ~^~~~~~~~~~~
izlet.cpp:34:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=i+1;j<ocs.size();++j){
                       ~^~~~~~~~~~~
izlet.cpp:39:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k=j+1;k<ocs.size();++k){
                               ~^~~~~~~~~~~
izlet.cpp:44:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int k=0;k<tc.size();++k){
                             ~^~~~~~~~~~
izlet.cpp: In function 'int main()':
izlet.cpp:94:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &t, &n);
     ~~~~~^~~~~~~~~~~~~~~~
izlet.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d", &colors[i][j]);
             ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 806 ms 44664 KB Output is correct
3 Correct 817 ms 44792 KB Output is correct
4 Correct 689 ms 41644 KB Output is correct
5 Correct 738 ms 44092 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 43284 KB Output is correct
2 Correct 754 ms 60644 KB Output is correct
3 Correct 959 ms 82372 KB Output is correct
4 Correct 1032 ms 83272 KB Output is correct
5 Correct 773 ms 56440 KB Output is correct
6 Correct 735 ms 65120 KB Output is correct
7 Correct 548 ms 53624 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 512 KB Output is correct
2 Correct 806 ms 44664 KB Output is correct
3 Correct 817 ms 44792 KB Output is correct
4 Correct 689 ms 41644 KB Output is correct
5 Correct 738 ms 44092 KB Output is correct
6 Correct 695 ms 43284 KB Output is correct
7 Correct 754 ms 60644 KB Output is correct
8 Correct 959 ms 82372 KB Output is correct
9 Correct 1032 ms 83272 KB Output is correct
10 Correct 773 ms 56440 KB Output is correct
11 Correct 735 ms 65120 KB Output is correct
12 Correct 548 ms 53624 KB Output is correct
13 Correct 853 ms 62932 KB Output is correct
14 Correct 946 ms 70260 KB Output is correct
15 Correct 764 ms 58708 KB Output is correct
16 Correct 854 ms 61912 KB Output is correct
17 Correct 820 ms 64432 KB Output is correct
18 Correct 701 ms 62400 KB Output is correct
19 Correct 896 ms 61908 KB Output is correct
20 Correct 795 ms 60708 KB Output is correct
21 Correct 840 ms 61612 KB Output is correct
22 Correct 856 ms 61532 KB Output is correct
23 Correct 880 ms 60860 KB Output is correct
24 Correct 841 ms 67452 KB Output is correct
25 Correct 715 ms 59068 KB Output is correct