제출 #862963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
862963		faustaadp	참나무 (IOI23_beechtree)	C++17	0 / 100	2067 ms	16988 KiB

beechtree

#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;
vector<pair<vector<ll>, vector<ll> > > glob;
ll te;
void dfs(ll pos, ll dpt)
{
    vector<ll> tmp;
    tmp.pb(-col[pos].size());
    tmp.pb(-dpt);
    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();
    // cout << pos << "  @@@\n";
    dfs(pos, 1);
    sort(glob.begin(), glob.end());
    do
    {
        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(i == 0)
                continue;
            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;
    }
    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;
}

컴파일 시 표준 에러 (stderr) 메시지

beechtree.cpp: In function 'll unik(std::vector<long long int>)':
beechtree.cpp:35: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]
   35 |     for(ll i = 1; i < X.size(); i++)
      |                   ~~^~~~~~~~~~
beechtree.cpp: In function 'll cari(ll)':
beechtree.cpp:67: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]
   67 |         for(ll i = 0; i < glob.size(); i++)
      |                       ~~^~~~~~~~~~~~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12