Submission #314146

#	Time	Username	Problem	Language	Result	Execution time	Memory
314146		lukameladze	슈퍼트리 잇기 (IOI20_supertrees)	C++14	21 / 100	267 ms	29280 KiB

supertrees

#include "supertrees.h"
#include <bits/stdc++.h>
using namespace std;
long long par[300005],a,bb,n,fix[300005];
int pa,sh;
//std::vector <std::vector <int> >  ans;
vector <long long> v[300005],v1;
int get_col(int a)
{
    if (par[a]==a) return a;
    par[a]=get_col(par[a]);
    return par[a];
}
void col(int a, int b)
{
    a=get_col(a);
    b=get_col(b);
    par[a]=b;
}
int construct(vector <vector <int> > p)
{
     int n=p.size();
     for (int i=0; i<n; i++)
   {
          par[i]=i;
     }
     for (int i=0; i<n; i++)
     {
          for (int j=0; j<n; j++)
          {
               if (p[i][j]==3)
               return 0;
          }
     }
     for (int i=0; i<n; i++)
    {
          for (int j=0; j<n; j++)
          {
               if (p[i][j]) col(i,j);
          }
     }
     for (int i=0; i<n; i++)
     {
         for (int j=0; j<n; j++)
         {
             if (get_col(i)==get_col(j) && !p[i][j]) return 0;
         }
     }
     
     for (int i=0; i<n;i++)
     {
          v[get_col(i)].push_back(i);
     }
     for (int i=0; i<n; i++)
     {
        if (!fix[get_col(i)])
        {
            v1.push_back(get_col(i)); 
            fix[get_col(i)]=1;              
        }
     }
     
    vector < vector < int > > ans(n, vector < int >(n, 0));
     for (int i=0; i<v1.size(); i++)
     {
         pa=v1[i];
         for (int j=0; j<v[pa].size(); j++)
         {
             sh=v[pa][j];
             if (sh!=pa)
             {
             ans[sh][pa]=1;
             ans[pa][sh]=1;
             }
         }
     }
     build(ans);
  return 1;
}

Compilation message (stderr)

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:64:21: 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 i=0; i<v1.size(); i++)
      |                    ~^~~~~~~~~~
supertrees.cpp:67:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |          for (int j=0; j<v[pa].size(); j++)
      |                        ~^~~~~~~~~~~~~

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