oj.uz

Submission #863108

# Submission time Handle Problem Language Result Execution time Memory
863108 2023-10-19T15:29:44 Z faustaadp Beech Tree (IOI23_beechtree) C++17
0 / 100
 2000 ms 53820 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 = 0;
        // 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] = 1;
            for(auto a : glob[i].se)
                if(jum[a] == 0)
                {
                    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++)
      |                       ~~^~~~~~~~~~~~~

Subtask #0
0.0 / 0.0

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

Subtask #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 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 16988 KB Output is correct
8 Correct 3 ms 17008 KB Output is correct
9 Incorrect 3 ms 16984 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 4 ms 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 4 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 78 ms 52592 KB Output is correct
8 Correct 79 ms 52368 KB Output is correct
9 Correct 6 ms 17244 KB Output is correct
10 Correct 3 ms 16984 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 16988 KB Output is correct
13 Correct 390 ms 20064 KB Output is correct
14 Correct 200 ms 19872 KB Output is correct
15 Correct 6 ms 19544 KB Output is correct
16 Correct 5 ms 19548 KB Output is correct
17 Execution timed out 2075 ms 53820 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 Incorrect 3 ms 16984 KB 2nd lines differ - on the 1st token, expected: '0', found: '1'
4 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 16984 KB Output is correct
2 Correct 4 ms 16988 KB Output is correct
3 Correct 3 ms 16988 KB Output is correct
4 Correct 3 ms 17008 KB Output is correct
5 Correct 78 ms 52592 KB Output is correct
6 Correct 79 ms 52368 KB Output is correct
7 Incorrect 3 ms 16984 KB 2nd lines differ - on the 74th token, expected: '0', found: '1'
8 Halted 0 ms 0 KB -

Subtask #5
0.0 / 14.0

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

Subtask #6
0.0 / 14.0

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

Subtask #8
0.0 / 17.0

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