Submission #117058

#	Time	Username	Problem	Language	Result	Execution time	Memory
117058		pavel	Izlet (COI19_izlet)	C++14	100 / 100	1032 ms	83272 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], 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 (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: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 / 18
• Subtask 2: 25 / 25
• Subtask 3: 57 / 57