Submission #955723

#	Time	Username	Problem	Language	Result	Execution time	Memory
955723		Alexabcde1	Connecting Supertrees (IOI20_supertrees)	C++14	56 / 100	192 ms	31536 KiB

supertrees

#include <vector>
#include <cstdio>
#include<bits/stdc++.h>
using namespace std;

void build(std::vector<std::vector<int>> b);
vector<long long> bg[1005],sg[1005];
vector<long long> kg;
long long a[1005],a2[1005],ans[1005][1005];
long long find(long long x){
    if (a[x]==x) return x;
    else return a[x]=find(a[x]);
}
long long find2(long long x){
    if (a2[x]==x) return x;
    else return a2[x]=find2(a2[x]);
}
void link(long long x,long long y){
    ans[x][y]=1;
    ans[y][x]=1;
    return;
}
int construct(std::vector<std::vector<int>> p) {
    long long n=p.size();
    for (int i=0;i<n;i++) a[i]=i;
    for (int i=0;i<n;i++) a2[i]=i;
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (p[i][j]==3) return 0;
            if (p[i][j]) {
                long long x=find(a[i]);
                long long y=find(a[j]);
                if (x!=y){
                    a[x]=y;
                }
            }
        }
    }
    for (int i=0;i<n;i++){
        for (int j=0;j<n;j++){
            if (p[i][j]==0) {
                long long x=find(a[i]);
                long long y=find(a[j]);
                if (x==y) return 0;
            }
        }
    }
    for (int i=0;i<n;i++){
        bg[find(i)].push_back(i);
    }
    for (int i=0;i<n;i++){
        for (int ii=0;ii<bg[i].size();ii++){
            for (int jj=0;jj<bg[i].size();jj++){
                long long u=bg[i][ii];
                long long v=bg[i][jj];
                long long x=find2(u);
                long long y=find2(v);
                if (p[u][v]==1){
                    a2[x]=y;
                }
            }
        }

        for (int ii=0;ii<bg[i].size();ii++){
            for (int jj=0;jj<bg[i].size();jj++){
                long long u=bg[i][ii];
                long long v=bg[i][jj];
                long long x=find2(u);
                long long y=find2(v);
                if (p[u][v]==2){
                    if (x==y) return 0;
                }
            }
        }

        for (int ii=0;ii<bg[i].size();ii++){
            sg[find2(bg[i][ii])].push_back(bg[i][ii]);
            //cout<<bg[i][ii]<<" "<<find2(bg[i][ii])<<endl;
        }
        kg.clear();
        for (int ii=0;ii<bg[i].size();ii++){
            long long node=bg[i][ii];
            if (sg[node].size()){
                for (int jj=0;jj<sg[node].size()-1;jj++){
                    link(sg[node][jj],sg[node][jj+1]);
                }
                kg.push_back(node);
            }
        }
        for (int i=0;i<kg.size();i++){
            if (kg.size()>1) link(kg[i],kg[(i+1)%kg.size()]);
        }

    }
    vector<vector<int> > anss;
    for (int i=0;i<n;i++){
        vector<int> tmp;
        for (int j=0;j<n;j++) tmp.push_back(ans[i][j]);
        anss.push_back(tmp);
    }
    build(anss);
    return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:52:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for (int ii=0;ii<bg[i].size();ii++){
      |                       ~~^~~~~~~~~~~~~
supertrees.cpp:53:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for (int jj=0;jj<bg[i].size();jj++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int ii=0;ii<bg[i].size();ii++){
      |                       ~~^~~~~~~~~~~~~
supertrees.cpp:65:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for (int jj=0;jj<bg[i].size();jj++){
      |                           ~~^~~~~~~~~~~~~
supertrees.cpp:76:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for (int ii=0;ii<bg[i].size();ii++){
      |                       ~~^~~~~~~~~~~~~
supertrees.cpp:81:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for (int ii=0;ii<bg[i].size();ii++){
      |                       ~~^~~~~~~~~~~~~
supertrees.cpp:84:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                 for (int jj=0;jj<sg[node].size()-1;jj++){
      |                               ~~^~~~~~~~~~~~~~~~~~
supertrees.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for (int i=0;i<kg.size();i++){
      |                      ~^~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 10 / 10
• Subtask 3: 0 / 19
• Subtask 4: 35 / 35
• Subtask 5: 0 / 21
• Subtask 6: 0 / 4