oj.uz

Submission #338627

# Submission time Handle Problem Language Result Execution time Memory
338627 2020-12-23T14:08:00 Z Dymo Uzastopni (COCI15_uzastopni) C++14
160 / 160
 55 ms 30100 KB 
#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

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.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1132 KB Output is correct
2 Correct 1 ms 1132 KB Output is correct
3 Correct 1 ms 1132 KB Output is correct
4 Correct 1 ms 1132 KB Output is correct
5 Correct 1 ms 1260 KB Output is correct
6 Correct 2 ms 1260 KB Output is correct
7 Correct 2 ms 1260 KB Output is correct
8 Correct 2 ms 1260 KB Output is correct
9 Correct 1 ms 1260 KB Output is correct
10 Correct 1 ms 1260 KB Output is correct
11 Correct 28 ms 17900 KB Output is correct
12 Correct 25 ms 17900 KB Output is correct
13 Correct 23 ms 18028 KB Output is correct
14 Correct 55 ms 30100 KB Output is correct
15 Correct 55 ms 29932 KB Output is correct
16 Correct 54 ms 29804 KB Output is correct
17 Correct 24 ms 18028 KB Output is correct
18 Correct 24 ms 18176 KB Output is correct
19 Correct 42 ms 22508 KB Output is correct
20 Correct 42 ms 22508 KB Output is correct