oj.uz

Submission #1090274

# Submission time Handle Problem Language Result Execution time Memory
1090274 2024-09-18T06:14:25 Z pmqwerty Magic Tree (CEOI19_magictree) C++17
9 / 100
 119 ms 7764 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
vector<int> a[MAXN];
int v[MAXN];
int w[MAXN];
int d[MAXN];
int n, m, k;
int par[MAXN];
int outdegree[MAXN];
namespace sub1{
    bool check(){
        if (!(n <= 20 && k <= 20)) return 0;
        for (int i = 1; i <= m; i++){
             if (w[i] > 1) return 0;
        }
        return 1;
    }
    int mark[21];
    bool flag = true;
    void dfs(int u, int t){
        if (mark[u]){
            if (d[u] > t){
                flag = false;
            }
        }
        for (int v: a[u]){
             dfs(v, (mark[u] ? d[u]: t));
        }
    }
    void solve(){
        int ans = 0;
        for (int mask = 0; mask < (1 << m); mask++){
             memset(mark, 0, sizeof(mark));
             for (int i = 0; i < m; i++){
                  if (mask & (1 << i)){
                      mark[v[i + 1]] = true;
                  }
             }
             flag = true;
             dfs(1, 1e9);
             if (flag){
                 if (ans < __builtin_popcount(mask)){
                     ans = __builtin_popcount(mask);
//                     for (int i = 0; i < m; i++){
//                          if (mask & (1 << i)){
//                              cout << v[i + 1] << " ";
//                          }
//                     }
//                     cout << '\n';
                 }

             }
        }
        cout << ans << '\n';
    }
}
namespace sub2{
    bool check(){
        for (int i = 1; i <= m; i++){
             if (outdegree[v[i]] != 0) return 0;
        }
        return 1;
    }
    void solve(){
        long long ans = 0;
        for (int i = 1; i <= m; i++){
             ans += w[i];
        }
        cout << ans << '\n';
    }
}
bool sub3_flag = true;
namespace sub3{
    bool check(){
        if (!sub3_flag) return false;
        for (int i = 1; i <= m; i++){
             if (w[i] > 1) return false;
        }
        return true;
    }
    int lis(vector<int> const& a) {
        int n = a.size();
        const int INF = 1e9;
        vector<int> l(n+1, INF);
        l[0] = -INF;
        for (int i = 0; i < n; i++) {
            int last = upper_bound(l.begin(), l.end(), a[i]) - l.begin();
            if (l[last-1] < a[i] && a[i] < l[last])
                l[last] = a[i];
        }

        int ans = 0;
        for (int i = 0; i <= n; i++) {
            if (l[i] < INF)
                ans = i;
        }
        return ans;
    }
    void solve(){
        vector<int> temp(n, 1e9);
        for (int i = 1; i <= m; i++){
             temp[v[i] - 1] = d[v[i]];
        }
        cout << lis(temp) << '\n';
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 2; i <= n; i++){
         int x;
         cin >> x;
         a[x].push_back(i);
         outdegree[x]++;
         sub3_flag &= ((x == (i - 1)));
    }
    for (int i = 1; i <= m; i++){
         cin >> v[i] >> d[v[i]] >> w[i];
    }
    if (sub1::check()) sub1::solve();
    else if (sub2::check()) sub2::solve();
    else if (sub3::check()) sub3::solve();
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 88 ms 2652 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 79 ms 2652 KB Output is correct
5 Correct 117 ms 2904 KB Output is correct
6 Correct 119 ms 2648 KB Output is correct
7 Correct 117 ms 2808 KB Output is correct
8 Correct 7 ms 2908 KB Output is correct
9 Correct 6 ms 2832 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 6172 KB Output is correct
2 Correct 15 ms 6716 KB Output is correct
3 Correct 26 ms 7244 KB Output is correct
4 Correct 23 ms 6364 KB Output is correct
5 Correct 26 ms 6992 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 28 ms 7764 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 88 ms 2652 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 79 ms 2652 KB Output is correct
5 Correct 117 ms 2904 KB Output is correct
6 Correct 119 ms 2648 KB Output is correct
7 Correct 117 ms 2808 KB Output is correct
8 Correct 7 ms 2908 KB Output is correct
9 Correct 6 ms 2832 KB Output is correct
10 Incorrect 26 ms 7400 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 3424 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 88 ms 2652 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 79 ms 2652 KB Output is correct
5 Correct 117 ms 2904 KB Output is correct
6 Correct 119 ms 2648 KB Output is correct
7 Correct 117 ms 2808 KB Output is correct
8 Correct 7 ms 2908 KB Output is correct
9 Correct 6 ms 2832 KB Output is correct
10 Incorrect 2 ms 2652 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #8
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2652 KB Output is correct
2 Correct 88 ms 2652 KB Output is correct
3 Correct 2 ms 2648 KB Output is correct
4 Correct 79 ms 2652 KB Output is correct
5 Correct 117 ms 2904 KB Output is correct
6 Correct 119 ms 2648 KB Output is correct
7 Correct 117 ms 2808 KB Output is correct
8 Correct 7 ms 2908 KB Output is correct
9 Correct 6 ms 2832 KB Output is correct
10 Correct 31 ms 6172 KB Output is correct
11 Correct 15 ms 6716 KB Output is correct
12 Correct 26 ms 7244 KB Output is correct
13 Correct 23 ms 6364 KB Output is correct
14 Correct 26 ms 6992 KB Output is correct
15 Incorrect 2 ms 2652 KB Output isn't correct
16 Halted 0 ms 0 KB -