oj.uz

Submission #132144

# Submission time Handle Problem Language Result Execution time Memory
132144 2019-07-18T10:51:17 Z stefdasca Uzastopni (COCI15_uzastopni) C++14
160 / 160
 105 ms 25720 KB 
#include<bits/stdc++.h>
using namespace std;
int n, val[10002];
vector<int> v[10002], q[112];
bitset<112>s[10002][112];
vector<pair<int, int> >r[10002];
void dfs(int nod)
{
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int vecin = v[nod][i];
        dfs(vecin);
    }
    for(int i = 0; i < 101; ++i)
        q[i].clear();
    for(int i = 0; i < v[nod].size(); ++i)
    {
        int x = v[nod][i];
        for(int j = 0; j < r[x].size(); ++j)
        {
            pair<int, int> ox = r[x][j];
            q[ox.first].push_back(ox.second);
        }
    }
    for(int i = 102; i >= 1; --i)
    {
        if(i == val[nod])
        {
            s[nod][i] |= s[nod][i + 1];
            s[nod][i].set(i);
        }
        else
        {
            for(int orz = 0; orz < q[i].size(); orz++)
            {
                int mx = q[i][orz];
                if(mx < val[nod] || i > val[nod])
                {
                  s[nod][i] |= s[nod][mx + 1];
                  s[nod][i].set(mx);
                }
            }
        }
        if(val[nod] >= i)
            for (int hi = 102; hi >= i; --hi)
                if (s[nod][i].test(hi) && val[nod] <= hi)
                    r[nod].emplace_back(i, hi);
    }
}
int main()
{
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> val[i];
    for(int i = 1; i < n; ++i)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
    }
    dfs(1);
    cout << r[1].size() << '\n';
    return 0;
}

Compilation message

uzastopni.cpp: In function 'void dfs(int)':
uzastopni.cpp:9:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
uzastopni.cpp:16:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < v[nod].size(); ++i)
                    ~~^~~~~~~~~~~~~~~
uzastopni.cpp:19:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < r[x].size(); ++j)
                        ~~^~~~~~~~~~~~~
uzastopni.cpp:34:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int orz = 0; orz < q[i].size(); orz++)
                              ~~~~^~~~~~~~~~~~~

Subtask #1
160.0 / 160.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 888 KB Output is correct
2 Correct 3 ms 888 KB Output is correct
3 Correct 3 ms 1016 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 3 ms 1016 KB Output is correct
6 Correct 3 ms 1016 KB Output is correct
7 Correct 4 ms 1016 KB Output is correct
8 Correct 4 ms 1016 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 58 ms 18880 KB Output is correct
12 Correct 51 ms 19028 KB Output is correct
13 Correct 47 ms 19064 KB Output is correct
14 Correct 105 ms 25720 KB Output is correct
15 Correct 105 ms 25676 KB Output is correct
16 Correct 104 ms 25720 KB Output is correct
17 Correct 47 ms 18936 KB Output is correct
18 Correct 47 ms 19064 KB Output is correct
19 Correct 94 ms 21272 KB Output is correct
20 Correct 94 ms 21368 KB Output is correct