oj.uz

Submission #863124

# Submission time Handle Problem Language Result Execution time Memory
863124 2023-10-19T16:18:15 Z faustaadp Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 52656 KB 
#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
const ll NN = 2e5 + 5;
vector<ll> v[NN];
vector<ll> col[NN];
ll ada[NN];
ll jum[NN];
ll idd[NN];
ll war[NN];
ll par[NN];
ll m;
ll NOW;
vector<pair<vector<ll>, vector<ll> > > glob;
ll te;
void dfs(ll pos, ll dpt)
{
    vector<ll> tmp;
    tmp.pb((pos != NOW));
    tmp.pb(-col[pos].size());
    tmp.pb(pos);
    // cout << pos << " POS\n";
    glob.pb(mp(tmp, col[pos]));
    for(auto nx : v[pos])
        dfs(nx, dpt + 1);
}
ll unik(vector<ll> X)
{
    sort(X.begin(), X.end());
    for(ll i = 1; i < X.size(); i++)
        if(X[i - 1] == X[i])
            return 0;
    return 1;
}
ll d[NN];
ll cari(ll pos)
{
    ll &ret = d[pos];
    if(ret != -1)
        return ret;
    ret = 1;
    for(auto nx : v[pos])
        if(!cari(nx))
        {
            ret = 0;
            break;
        }
    if(!ret)return ret;

    if(!unik(col[pos]))ret = 0;
    if(!ret)return ret;

    glob.clear();
    NOW = pos;
    // cout << pos << "  @@@\n";
    dfs(pos, 1);
    sort(glob.begin(), glob.end());
    // do
    {
        ret = 1;
        // if(pos == 0)cout << "\n";
        ll oi = 1;
        for(ll i = 1; i <= m; i++)
            jum[i] = 0;
        for(ll i = 0; i < glob.size(); i++)
            idd[glob[i].fi[2]] = i;

        // if(glob[0].fi[2] != pos)
            // continue;
        for(ll i = 0; i < glob.size(); i++)
        {
            // idd[glob[i].fi[2]] = i;
            // if(pos == 0)cout << glob[i].fi[2] << "  _\n";
            if(i == 0)
                continue;

            for(auto a : glob[i - 1].se)
                jum[a] = i;
            for(auto a : glob[i].se)
                if(jum[a] != i)
                {
                    ret = 0;
                    return ret;
                }
            // if(pos == 4)cout << idd[par[glob[i].fi[2]]] << " dan " << jum[war[glob[i].fi[2]]] << "_\n";
            // if(idd[par[glob[i].fi[2]]] != jum[war[glob[i].fi[2]]])
            // {
            //     oi = 0;
            //     break;
            // }
            // jum[war[glob[i].fi[2]]]++;
            // if(!oi)break;
        }
        // if(oi)ret = 1;
        // if(oi)
        // {
        //     // cout << "YES\n";
        //     break;
        // }
    }
    // while(next_permutation(glob.begin(), glob.end()));
    
    return ret;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
    m = M;
    memset(d, -1, sizeof(d));
    vector<int> ret(N, 0);
    for(ll i = 1; i < N; i++)
    {
        v[P[i]].pb(i);
        col[P[i]].pb(C[i]);
        par[i] = P[i];
        war[i] = C[i];
    }
    // dfs(0, 0);
    for(ll i = 0; i < N; i++)
    {
        ret[i] = cari(i);
        // cout << i << " " << cari(i) << "\n";
    }
    // for(ll i = 0; i <)
    // {
    //     vector<ll> tmp;
    //     for(auto a : v[0])
    //     {
    //         ada[a.se] = 1;
    //         tmp.pb(a.se);
    //     }
    //     sort(tmp.begin(), tmp.end());
    //     for(ll j = 1; j < tmp.size(); j++)
    //         if(tmp[j - 1] == tmp[j])
    //             ret[0] = 0;
    // }

    // vector<pair<ll, vector<ll> > > vv;
    // for(ll i = 1; i < N; i++)
    //     if(v[i].size() == 0)
    //         ret[i] = 1;
    //     else
    //     {
    //         ret[i] = 1;
    //         vector<ll> tmp;
    //         for(auto a : v[i])
    //             tmp.pb(a.se);
    //         sort(tmp.begin(), tmp.end());
    //         for(ll j = 0; j < tmp.size(); j++)
    //         {
    //             if(!ada[tmp[j]])
    //                 ret[0] = 0;
    //         }
    //         for(ll j = 1; j < tmp.size(); j++)
    //             if(tmp[j - 1] == tmp[j])
    //             {
    //                 ret[0] = 0;
    //                 ret[i] = 0;
    //             }
    //         vv.pb(mp((ll)tmp.size(), tmp));
    //     }
    // sort(vv.begin(), vv.end());
    
    return ret;
}

Compilation message

beechtree.cpp: In function 'll unik(std::vector<long long int>)':
beechtree.cpp:36:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(ll i = 1; i < X.size(); i++)
      |                   ~~^~~~~~~~~~
beechtree.cpp: In function 'll cari(ll)':
beechtree.cpp:71:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::vector<long long int>, std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(ll i = 0; i < glob.size(); i++)
      |                       ~~^~~~~~~~~~~~~
beechtree.cpp:76:25: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<std::vector<long long int>, std::vector<long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |         for(ll i = 0; i < glob.size(); i++)
      |                       ~~^~~~~~~~~~~~~
beechtree.cpp:68:12: warning: unused variable 'oi' [-Wunused-variable]
   68 |         ll oi = 1;
      |            ^~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Incorrect 3 ms 17080 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16984 KB Output is correct
8 Correct 3 ms 16984 KB Output is correct
9 Incorrect 3 ms 16988 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
10 Halted 0 ms 0 KB -

Subtask #2
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Correct 4 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 76 ms 51280 KB Output is correct
8 Correct 94 ms 51280 KB Output is correct
9 Correct 8 ms 17400 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 396 ms 20008 KB Output is correct
14 Correct 207 ms 19892 KB Output is correct
15 Correct 6 ms 19548 KB Output is correct
16 Correct 4 ms 19292 KB Output is correct
17 Execution timed out 2089 ms 52656 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 16988 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 3 ms 16984 KB Output is correct
8 Correct 3 ms 16984 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Correct 3 ms 16988 KB Output is correct
11 Correct 34 ms 19372 KB Output is correct
12 Correct 26 ms 19288 KB Output is correct
13 Correct 28 ms 19292 KB Output is correct
14 Correct 28 ms 19280 KB Output is correct
15 Execution timed out 2055 ms 23856 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Correct 76 ms 51280 KB Output is correct
6 Correct 94 ms 51280 KB Output is correct
7 Correct 3 ms 16988 KB Output is correct
8 Correct 3 ms 16988 KB Output is correct
9 Correct 46 ms 19292 KB Output is correct
10 Correct 45 ms 19308 KB Output is correct
11 Execution timed out 2067 ms 28564 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Incorrect 3 ms 17080 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #6
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Incorrect 3 ms 16988 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #7
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Incorrect 3 ms 17080 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 3 ms 16984 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Incorrect 3 ms 16988 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
6 Halted 0 ms 0 KB -

Subtask #9
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Incorrect 3 ms 17080 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -