oj.uz

Submission #863127

# Submission time Handle Problem Language Result Execution time Memory
863127 2023-10-19T16:20:01 Z faustaadp Beech Tree (IOI23_beechtree) C++17
17 / 100
 2000 ms 51284 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 = 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;
            te++;
            for(auto a : glob[i - 1].se)
                jum[a] = te;
            for(auto a : glob[i].se)
                if(jum[a] != te)
                {
                    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:69: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]
   69 |         for(ll i = 0; i < glob.size(); i++)
      |                       ~~^~~~~~~~~~~~~
beechtree.cpp:74: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]
   74 |         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 16984 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 #1
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17240 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 4 ms 17244 KB Output is correct
4 Correct 3 ms 16984 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 16988 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 17240 KB Output is correct
2 Correct 3 ms 16988 KB Output is correct
3 Correct 4 ms 17244 KB Output is correct
4 Correct 3 ms 16984 KB Output is correct
5 Correct 3 ms 16988 KB Output is correct
6 Correct 3 ms 16988 KB Output is correct
7 Correct 119 ms 51284 KB Output is correct
8 Correct 77 ms 51092 KB Output is correct
9 Correct 6 ms 17240 KB Output is correct
10 Correct 4 ms 16984 KB Output is correct
11 Correct 3 ms 16988 KB Output is correct
12 Correct 3 ms 17068 KB Output is correct
13 Correct 334 ms 20012 KB Output is correct
14 Correct 165 ms 19692 KB Output is correct
15 Correct 4 ms 19544 KB Output is correct
16 Correct 4 ms 19292 KB Output is correct
17 Execution timed out 2069 ms 50476 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16984 KB Output is correct
2 Correct 5 ms 16988 KB Output is correct
3 Correct 6 ms 11356 KB Output is correct
4 Correct 5 ms 11356 KB Output is correct
5 Correct 6 ms 11356 KB Output is correct
6 Correct 6 ms 11356 KB Output is correct
7 Correct 6 ms 11352 KB Output is correct
8 Correct 6 ms 11352 KB Output is correct
9 Correct 5 ms 11356 KB Output is correct
10 Correct 5 ms 11352 KB Output is correct
11 Correct 8 ms 11820 KB Output is correct
12 Correct 4 ms 19288 KB Output is correct
13 Correct 4 ms 19292 KB Output is correct
14 Correct 4 ms 19300 KB Output is correct
15 Correct 99 ms 33156 KB Output is correct
16 Correct 95 ms 29952 KB Output is correct
17 Correct 104 ms 33792 KB Output is correct
18 Correct 113 ms 30464 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17240 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 119 ms 51284 KB Output is correct
6 Correct 77 ms 51092 KB Output is correct
7 Correct 3 ms 16984 KB Output is correct
8 Correct 4 ms 16988 KB Output is correct
9 Correct 6 ms 19292 KB Output is correct
10 Correct 5 ms 19292 KB Output is correct
11 Correct 122 ms 29460 KB Output is correct
12 Correct 125 ms 30048 KB Output is correct

Subtask #5
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 Incorrect 3 ms 16984 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 17240 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 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 16984 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 #8
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 17240 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 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 16984 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 -