Submission #116696

#	Time	Username	Problem	Language	Result	Execution time	Memory
116696		pavel	Izlet (COI19_izlet)	C++14	0 / 100	763 ms	43408 KiB

izlet

#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], lc[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(){
    for(int i=0;i<n;++i){
        if(!c[i]){
            queue<int> todo;
            todo.push(i);
            par[i]=-1;
            while(!todo.empty()){
                int curr=todo.front();
                todo.pop();

                if(par[curr]==-1 || colors[lc[curr]][par[curr]]==colors[lc[curr]][curr]){
                    c[curr]=i+1;
                    lc[curr]=curr;
                }

                for(auto j:graph[curr]){
                    if(j!=par[curr]){
                        par[j]=curr;
                        lc[j]=lc[curr];
                        todo.push(j);
                    }
                }
            }
        }
    }
}

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 (stderr)

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:86: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:89: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: 0 / 18
• Subtask 2: 0 / 25
• Subtask 3: 0 / 57