oj.uz

Submission #294471

# Submission time Handle Problem Language Result Execution time Memory
294471 2020-09-09T00:22:29 Z albertolg101 Split the Attractions (IOI19_split) C++17
11 / 100
 673 ms 1048580 KB 
#include<bits/stdc++.h>
#include "split.h"

using namespace std;

vector<int> a_is_equal_to_one (int b, int c, int n, vector<vector<int>> &G)
{
    vector<bool> flag(n); 
    int cnt = 1;

    function<void(int)> dfs1 = [&]( int nod )
    {
        for(auto i: G[nod])
        {
            if( cnt == b ) 
                return ;

            if(flag[i])
                continue; 

            flag[i] = 1; 
            cnt++; 

            dfs1(i); 
        }
    } ;

    flag[0] = true; 
    dfs1(0); 

    bool a = false ; 
    vector<int> ans(n);

    for( int i = 0 ; i < n ; i++ )
    {
        if( flag[i] ) 
            ans[i] = 2 ; 
        
        else if( a )
            ans[i] = 3 ; 
        
        else
            ans[i] = 1, a = true; 
    }

    return ans ; 
}

vector<int> is_a_line (int a, int b, int c, int n, vector<vector<int>> &G)
{
    int root = 0;
    for( int i = 0 ; i < n ; i++ ) 
        if( G[i].size() == 1 ) 
            root = i ; 

    vector<int> ans(n);

    function<void(int, int, int)> dfs = [&](int nod, int father, int lvl)
    {
        if( lvl <= a ) 
            ans[nod] = 1; 
        
        else if( lvl <= a + b ) 
            ans[nod] = 2 ;
        
        else 
            ans[nod] = 3 ; 

        for( auto target : G[nod] )
        {
            if( target != father )
                dfs( target , nod , lvl + 1 ) ; 
        }
    } ;
    
    dfs(root, -1, 1);

    return ans;
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    
    vector<vector<int>> G(n + 1);
    int m = p.size(), degree = 0; 

    for(int i = 0; i < m; i++)
    {
        G[p[i]].push_back(q[i]);
        G[q[i]].push_back(p[i]);

        degree = max({ degree, (int)G[p[i]].size() , (int)G[q[i]].size() });
    }

    if(a == 1) 
        return a_is_equal_to_one(b, c, n, G); 

    else 
        return is_a_line(a, b, c, n, G);

}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 1 ms 256 KB ok, correct split
3 Correct 0 ms 256 KB ok, correct split
4 Runtime error 672 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB ok, correct split
2 Correct 1 ms 256 KB ok, correct split
3 Correct 1 ms 256 KB ok, correct split
4 Correct 99 ms 10624 KB ok, correct split
5 Correct 82 ms 9080 KB ok, correct split
6 Correct 78 ms 8952 KB ok, correct split
7 Correct 86 ms 12024 KB ok, correct split
8 Correct 128 ms 12408 KB ok, correct split
9 Correct 83 ms 8952 KB ok, correct split
10 Correct 60 ms 8944 KB ok, correct split
11 Correct 60 ms 8944 KB ok, correct split
12 Correct 63 ms 9328 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 256 KB invalid split: #1=2, #2=2, #3=1
2 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 673 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB ok, correct split
2 Correct 1 ms 256 KB ok, correct split
3 Correct 0 ms 256 KB ok, correct split
4 Runtime error 672 ms 1048576 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -