Submission #338627

#	Time	Username	Problem	Language	Result	Execution time	Memory
338627		Dymo	Uzastopni (COCI15_uzastopni)	C++14	160 / 160	55 ms	30100 KiB

uzastopni

#include<bits/stdc++.h>
using namespace std;


#define pb  push_back
#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define endl "\n"
const ll maxn=1e4+5;
const ll mod =998244353 ;
const ll maxn1=51;
const ll base=1e9;
vector<ll> adj[maxn];
vector<ll> adj1[maxn];
bitset<102> bit[maxn][102];
vector<pll> adj2[maxn];
ll a[maxn];
void dfs(ll u,ll par)
{
    for (auto to:adj[u])
    {
        if (to==par) continue;
        dfs(to,u);
    }
    for(int i=1;i<=100;i++)
    {
        adj1[i].clear();
    }
    for (auto to:adj[u])
    {
        if(to==par) continue;
        for (auto p:adj2[to])
        {
            adj1[p.ff].pb(p.ss);
        }
    }
    for (int i=100;i>=1;i--)
    {
        if (i==a[u])
        {
             bit[u][i].set(i);
             bit[u][i]|=bit[u][i+1];
        }
        else if (i>a[u])
        {
            for (auto p:adj1[i])
            {
                bit[u][i].set(p);
                bit[u][i]|=bit[u][p+1];
            }
        }
        else
        {
            for (auto p:adj1[i])
            {
                if (p<a[u])
                {
                    bit[u][i].set(p);
                    bit[u][i]|=bit[u][p+1];
                }
            }
        }
    }
    for (int l=1;l<=a[u];l++)
    {
        for (int r=a[u];r<=100;r++)
        {
            if (bit[u][l][r])
            {
                adj2[u].pb(make_pair(l,r));
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    if (fopen("GIFT11.inp","r"))
    {
        freopen("GIFT11.inp","r",stdin);
        freopen("GIFT11.out","w",stdout);
    }
    ll n;
    cin>>n ;
    for (int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for (int i=1;i<=n-1;i++)
    {
        ll x, y;
         cin>> x>> y;
         adj[x].pb(y);
         adj[y].pb(x);
    }
    dfs(1,0);
    cout <<adj2[1].size();


}

Compilation message (stderr)

uzastopni.cpp: In function 'int main()':
uzastopni.cpp:84:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   84 |         freopen("GIFT11.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
uzastopni.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   85 |         freopen("GIFT11.out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 160 / 160