oj.uz

Submission #733705

# Submission time Handle Problem Language Result Execution time Memory
733705 2023-05-01T08:18:32 Z tigar Connecting Supertrees (IOI20_supertrees) C++14
21 / 100
 953 ms 2097152 KB 
#include <bits/stdc++.h>
#include "supertrees.h"

using namespace std;

typedef long long ll;
vector<int> jedan[1010], dva[1010], nula[1010];
bool check[1010];
vector<int>lin;
vector<int>cc[1010];

bool provera(int x, std::vector<std::vector<int>>p, int cmp)
{
    lin.push_back(x);
    cc[cmp].push_back(x);
    int n=p.size();
    for(int i=0; i<jedan[x].size(); i++)
    {
        if(check[jedan[x][i]])continue;
        check[jedan[x][i]]=true;
        if(jedan[x].size()!=jedan[jedan[x][i]].size())return false;
        for(int j=0; j<jedan[x].size(); j++)
        {
            if(jedan[x][j]!=jedan[jedan[x][i]][j])return false;
        }
    }
    for(int i=0; i<dva[x].size(); i++)
    {
        if(check[dva[x][i]])continue;
        check[dva[x][i]]=true;
        if(nula[x].size()!=nula[dva[x][i]].size())return false;
        if(nula[x].size()<=n/2)
        {for(int j=0; j<nula[x].size(); j++)
        {
            if(nula[x][j]!=nula[dva[x][i]][j])return false;
        }}
        else
        {
            for(int j=0; j<jedan[x].size(); j++)
            {
                if(jedan[x][j]!=0 and jedan[dva[x][i]][j]==0)return false;
                if(jedan[x][j]==0 and jedan[dva[x][i]][j]!=0)return false;
            }
            for(int j=0; j<dva[x].size(); j++)
            {
                if(dva[x][j]!=0 and dva[dva[x][i]][j]==0)return false;
                if(dva[x][j]==0 and dva[dva[x][i]][j]!=0)return false;
            }
        }
        if(!provera(dva[x][i], p, cmp))return false;
    }
    return true;
}

int construct(std::vector<std::vector<int>>p)
{
    int n=p.size();
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            if(p[i][j]==1)jedan[i].push_back(j);
            else if(p[i][j]==2)dva[i].push_back(j);
            else if(p[i][j]==3)return 0;
            else nula[i].push_back(j);
        }
    }
    int br=1;
    for(int i=0; i<n; i++)
    {
        if(check[i])continue;
        if(!provera(i, p, br))return 0;
        br++;
    }
    vector<vector<int> > ans(n);
    for(int i=0; i<n; i++){ans[i].resize(n, 0);}
    for(int i=0; i<lin.size(); i++)
    {
        for(int j=1; j<jedan[lin[i]].size(); j++)
        {
            ans[jedan[lin[i]][j]][jedan[lin[i]][j-1]]=1;
            ans[jedan[lin[i]][j-1]][jedan[lin[i]][j]]=1;
        }
    }

    for(int i=1; i<br; i++)
    {
        for(int j=0; j<cc[i].size(); j++)
        {
            //cout<<cc[i][j]<<" ";
            if(cc[i].size()==2)return 0;
            ans[cc[i][j]][cc[i][(j+1)%cc[i].size()]]=1;
            ans[cc[i][(j+1)%cc[i].size()]][cc[i][j]]=1;
        }
        //cout<<endl;
    }
    for(int i=0; i<n; i++)
    {
        ans[i][i]=0;
    }
    //for(int i=0; i<n; i++){for(int j=0; j<n; j++)cout<<ans[i][j]<<" "; cout<<endl;}
    build(ans);
    return 1;
}

/*int main()
{
    int n; cin>>n;
    vector<vector<int> >p;
    for(int i=0; i<n; i++)
    {
        vector<int>pp(n);
        for(int j=0; j<n; j++)
        {
            cin>>pp[j];
        }
        p.push_back(pp);
    }
    cout<<construct(p);
}
*/

Compilation message

supertrees.cpp: In function 'bool provera(int, std::vector<std::vector<int> >, int)':
supertrees.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for(int i=0; i<jedan[x].size(); i++)
      |                  ~^~~~~~~~~~~~~~~~
supertrees.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int j=0; j<jedan[x].size(); j++)
      |                      ~^~~~~~~~~~~~~~~~
supertrees.cpp:27:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0; i<dva[x].size(); i++)
      |                  ~^~~~~~~~~~~~~~
supertrees.cpp:32:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         if(nula[x].size()<=n/2)
      |            ~~~~~~~~~~~~~~^~~~~
supertrees.cpp:33:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         {for(int j=0; j<nula[x].size(); j++)
      |                       ~^~~~~~~~~~~~~~~
supertrees.cpp:39:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |             for(int j=0; j<jedan[x].size(); j++)
      |                          ~^~~~~~~~~~~~~~~~
supertrees.cpp:44:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int j=0; j<dva[x].size(); j++)
      |                          ~^~~~~~~~~~~~~~
supertrees.cpp: In function 'int construct(std::vector<std::vector<int> >)':
supertrees.cpp:77:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |     for(int i=0; i<lin.size(); i++)
      |                  ~^~~~~~~~~~~
supertrees.cpp:79:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int j=1; j<jedan[lin[i]].size(); j++)
      |                      ~^~~~~~~~~~~~~~~~~~~~~
supertrees.cpp:88:23: 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=0; j<cc[i].size(); j++)
      |                      ~^~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 1532 KB Output is correct
7 Correct 172 ms 27984 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 1532 KB Output is correct
7 Correct 172 ms 27984 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 10 ms 1560 KB Output is correct
13 Correct 772 ms 27548 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 4 ms 1152 KB Output is correct
17 Correct 86 ms 19028 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 47 ms 7392 KB Output is correct
21 Correct 183 ms 28084 KB Output is correct
22 Correct 454 ms 27592 KB Output is correct
23 Correct 178 ms 27400 KB Output is correct
24 Correct 803 ms 27472 KB Output is correct
25 Correct 80 ms 18884 KB Output is correct
26 Correct 117 ms 18356 KB Output is correct
27 Correct 193 ms 29456 KB Output is correct
28 Correct 769 ms 27672 KB Output is correct

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 10 ms 1536 KB Output is correct
9 Correct 739 ms 27464 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 26 ms 33896 KB Output is correct
13 Runtime error 953 ms 2097152 KB Execution killed with signal 9
14 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 68 ms 6984 KB Output is correct
5 Correct 212 ms 26736 KB Output is correct
6 Correct 498 ms 26180 KB Output is correct
7 Correct 187 ms 26100 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Incorrect 18 ms 4372 KB Answer gives possible 0 while actual possible 1
10 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 1532 KB Output is correct
7 Correct 172 ms 27984 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 10 ms 1560 KB Output is correct
13 Correct 772 ms 27548 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 4 ms 1152 KB Output is correct
17 Correct 86 ms 19028 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 47 ms 7392 KB Output is correct
21 Correct 183 ms 28084 KB Output is correct
22 Correct 454 ms 27592 KB Output is correct
23 Correct 178 ms 27400 KB Output is correct
24 Correct 803 ms 27472 KB Output is correct
25 Correct 80 ms 18884 KB Output is correct
26 Correct 117 ms 18356 KB Output is correct
27 Correct 193 ms 29456 KB Output is correct
28 Correct 769 ms 27672 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 10 ms 1536 KB Output is correct
37 Correct 739 ms 27464 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 26 ms 33896 KB Output is correct
41 Runtime error 953 ms 2097152 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 7 ms 1532 KB Output is correct
7 Correct 172 ms 27984 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 10 ms 1560 KB Output is correct
13 Correct 772 ms 27548 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 4 ms 1152 KB Output is correct
17 Correct 86 ms 19028 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 47 ms 7392 KB Output is correct
21 Correct 183 ms 28084 KB Output is correct
22 Correct 454 ms 27592 KB Output is correct
23 Correct 178 ms 27400 KB Output is correct
24 Correct 803 ms 27472 KB Output is correct
25 Correct 80 ms 18884 KB Output is correct
26 Correct 117 ms 18356 KB Output is correct
27 Correct 193 ms 29456 KB Output is correct
28 Correct 769 ms 27672 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 10 ms 1536 KB Output is correct
37 Correct 739 ms 27464 KB Output is correct
38 Correct 1 ms 340 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 26 ms 33896 KB Output is correct
41 Runtime error 953 ms 2097152 KB Execution killed with signal 9
42 Halted 0 ms 0 KB -