oj.uz

Submission #1114838

# Submission time Handle Problem Language Result Execution time Memory
1114838 2024-11-19T16:58:18 Z kokoue Connecting Supertrees (IOI20_supertrees) C++14
11 / 100
 160 ms 24136 KB 
#include<bits/stdc++.h>
#include "supertrees.h"
#define maxn 1010
#define f first
#define s second
using namespace std;
int is[maxn];
vector<pair<int,int>> comp[maxn];
int par[maxn];
int findd(int u)
{
    if(par[u]==-1) return u;
    return par[u]=findd(par[u]);
}
void unite(int u,int v)
{
    u=findd(u);
    v=findd(v);
    if(v==u) return;
    if(comp[u].size()<comp[v].size()) swap(u,v);
    for(auto e:comp[v]) comp[u].push_back(e);
    par[v]=u;
    comp[v].clear();
}
vector<vector<int>> d;
int construct(vector<vector<int>> p)
{
    int n=p.size();
    for(int i=0;i<n;i++)
    {
        par[i]=-1;
        int cntr=0;
        vector<int> dumbbb(n,0);
        d.push_back(dumbbb);
        for(auto e:p[i])
        {
            if(e==1) cntr++;
        }
        is[i]=1;

        if(cntr==1) is[i]=2;
        comp[i].push_back({is[i],i});
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(i==j) continue;
            if(p[i][j]) unite(i,j);
        }
    }
    for(int i=0;i<n;i++)
    {
        if(comp[i].size()==0 || comp[i].size()==1) continue;

        sort(comp[i].begin(),comp[i].end());

        int prev=-1;
        int last=-1;

        for(auto e:comp[i])
        {

            if(e.f==1) last=e.s;

            if(prev==-1)
            {
                prev=e.s;

                continue;

            }
            d[prev][e.s]=1;
            d[e.s][prev]=1;
            prev=e.s;
        }
        if(comp[i][comp[i].size()-1].f==1) continue;
        if(last==-1)
        {
            d[comp[i][comp[i].size()-1].s] [comp[i][0].s]=1;
            d[comp[i][0].s] [comp[i][comp[i].size()-1].s]=1;
        }
        else
        {
            d[comp[i][comp[i].size()-1].s] [last]=1;
            d[last] [comp[i][comp[i].size()-1].s]=1;
        }
    }

    build(d);
    return 1;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 11 ms 1372 KB Output is correct
7 Correct 140 ms 22076 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 11 ms 1372 KB Output is correct
7 Correct 140 ms 22076 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 6 ms 1528 KB Output is correct
13 Correct 130 ms 22088 KB Output is correct
14 Incorrect 1 ms 336 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Incorrect 1 ms 508 KB Answer gives possible 1 while actual possible 0
5 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 41 ms 6216 KB Output is correct
5 Correct 160 ms 22060 KB Output is correct
6 Correct 141 ms 23368 KB Output is correct
7 Correct 145 ms 23408 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 35 ms 6216 KB Output is correct
10 Correct 145 ms 24136 KB Output is correct
11 Correct 126 ms 24084 KB Output is correct
12 Correct 135 ms 24136 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Incorrect 34 ms 6372 KB Too few ways to get from 0 to 24, should be 2 found 1
17 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 11 ms 1372 KB Output is correct
7 Correct 140 ms 22076 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 6 ms 1528 KB Output is correct
13 Correct 130 ms 22088 KB Output is correct
14 Incorrect 1 ms 336 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -

Subtask #6
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 11 ms 1372 KB Output is correct
7 Correct 140 ms 22076 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 6 ms 1528 KB Output is correct
13 Correct 130 ms 22088 KB Output is correct
14 Incorrect 1 ms 336 KB Answer gives possible 1 while actual possible 0
15 Halted 0 ms 0 KB -