oj.uz

Submission #317825

# Submission time Handle Problem Language Result Execution time Memory
317825 2020-10-30T12:57:09 Z akobi Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 302 ms 22136 KB 
#include "supertrees.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int find_set(int u,vector<int> &p) 
{
    if (u==p[u])
        return u;
    return p[u]=find_set(p[u],p);
}
void union_set(int u,int v,vector <int> &p) 
{
    u=find_set(u,p);
    v=find_set(v,p);
    p[u]=v;
    return;
}
int n,u,v;
vector<int> p,pp,t,fix,s;
vector< vector<int> > b,g;
int construct( vector<vector<int>> a ) 
{
    n=a.size();
    for (int i=0; i<n; i++)
        p.pb(i);
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++) 
        {
            if (a[i][j]==3)
                return 0;
            if (a[i][j]>0)
                union_set(i,j,p);
        }
    for (int i=0; i<n; i++) 
        for (int j=0; j<n; j++) 
        {
            u=find_set(i,p);
            v=find_set(j,p);
            if (u==v && a[i][j]==0) 
                return 0;
        }
    for (int i=0; i<n; i++)
        g.pb(t);
    for (int i=0; i<n; i++)
    {
        u=find_set(i,p);
        g[u].pb(i);
    }
    for (int i=0; i<n; i++) 
        pp.pb(i);
    for (int i=0; i<n; i++)
        t.pb(0);
    for (int i=0; i<n; i++)
        b.pb(t);
    for (int i=0; i<n; i++) 
    {
        if (g[i].empty()) 
            continue;
        for (int x=0; x<g[i].size(); x++)
            for (int y=x; y<g[i].size(); y++)
                if (a[ g[i][x] ][ g[i][y] ] == 1)
                    union_set(x, y, pp);
        
        for (int x=0; x<g[i].size(); x++)
            for (int y=x; y<g[i].size(); y++)
            {
                u=find_set(g[i][x],pp);
                v=find_set(g[i][y],pp);
                if (u==v && a[x][y]==2)
                    return 0;
            }
        for (int x=0; x<n; x++)
            fix.pb(-1);
        for (int x=0; x<g[i].size(); x++) 
        {
            u=find_set(g[i][x],pp);
            if (fix[u]!=-1) 
            {
                b[ fix[u] ][ g[i][x] ]=1;
                b[ g[i][x] ][ fix[u] ]=1; 
            }
            fix[u]=g[i][x];
            if (g[i][x]==u)
                s.pb(x);
        }
        if (s.size()==2)
            return 0;
        for (int j=1; j<s.size(); j++) 
        {
            u=s[j-1];
            v=s[j];
            b[u][v]=1;
            b[v][u]=1;
        }
        u=s[ s.size()-1 ];
        v=s[0];
        if (u!=v)
        {
            b[u][v]=1;
            b[v][u]=1;
        }
    }
    build(b);
    return 1;
}

Compilation message

supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:59:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int x=0; x<g[i].size(); x++)
      |                       ~^~~~~~~~~~~~
supertrees.cpp:60:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |             for (int y=x; y<g[i].size(); y++)
      |                           ~^~~~~~~~~~~~
supertrees.cpp:64:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int x=0; x<g[i].size(); x++)
      |                       ~^~~~~~~~~~~~
supertrees.cpp:65:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for (int y=x; y<g[i].size(); y++)
      |                           ~^~~~~~~~~~~~
supertrees.cpp:74:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         for (int x=0; x<g[i].size(); x++)
      |                       ~^~~~~~~~~~~~
supertrees.cpp:88:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for (int j=1; j<s.size(); j++)
      |                       ~^~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1280 KB Output is correct
7 Correct 302 ms 22136 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1280 KB Output is correct
7 Correct 302 ms 22136 KB Output is correct
8 Incorrect 1 ms 256 KB Answer gives possible 0 while actual possible 1
9 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB Answer gives possible 0 while actual possible 1
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1280 KB Output is correct
7 Correct 302 ms 22136 KB Output is correct
8 Incorrect 1 ms 256 KB Answer gives possible 0 while actual possible 1
9 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 11 ms 1280 KB Output is correct
7 Correct 302 ms 22136 KB Output is correct
8 Incorrect 1 ms 256 KB Answer gives possible 0 while actual possible 1
9 Halted 0 ms 0 KB -