제출 #1186552

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1186552		omar1312	9월 (APIO24_september)	C++20	0 / 100	2 ms	2884 KiB

september

#include "september.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const ll mod = 1000000007;
const ll N = 100001;
int a[N+2], dp[N+2], dep[N+2], sub[N+2], id[N+2], ord[N+2], near[N+2];
vector<int> adj[N+2], order;
struct Segtree{
    vector<int> t;
    int off = 1;
    Segtree(int n){
        while(off < n)off <<= 1;
        t.resize(2 * off, 0);
    };
    void update(int u, int v, int tp){
        t[u += off] = v;
        if(!tp)while(u >>= 1)t[u] = t[u * 2] + t[u * 2 + 1];
        else while(u >>= 1)t[u] = max(t[u * 2], t[u * 2 + 1]);
    }
    int query(int n, int ql, int qh, int nl, int nh, int tp){
        if(ql <= nl && nh <= qh)return t[n];
        if(nl > qh || ql > nh)return 0;
        int m = (nl + nh) / 2;
        if(!tp)return query(n * 2, ql, qh, nl, m, tp) + query(n * 2 + 1, ql, qh, m + 1, nh, tp);
        else return max(query(n * 2, ql, qh, nl, m, tp), query(n * 2 + 1, ql, qh, m + 1, nh, tp));
    }
};
void dfs(int u, int par, int d){
    dep[u] = d;
    sub[u] = 1;
    ord[u] = order.size();
    order.pb(u);
    for(auto &v : adj[u]){
        if(v == par)continue;
        dfs(v, u, d + 1);
        sub[u] += sub[v];
    }
}
int solve(int n, int m, std::vector<int> f, std::vector<std::vector<int>> s){
    for(int i = 1; i < n; i++){
        adj[f[i]].pb(i);
        adj[i].pb(f[i]);
    }
    dfs(0, 0, 0);
    vector<Segtree> segtree(m, Segtree(n));
    Segtree mid(n);
    for(int j = 0; j < m; j++){
        for(int i = 0; i < n - 1; i++){
            id[s[j][i]] = max(id[s[j][i]], i);
        }
    }
    stack<int> st;
    for(int i = n - 1; i >= 0; i--){
        while(!st.empty() && dep[order[st.top()]] > dep[order[i]])st.pop();
        if(st.empty())near[i] = i;
        else near[i] = st.top() - 1;
        st.push(i);
    }
    for(int i = 0; i < n - 1; i++){
        mid.update(ord[s[0][i]], id[s[0][i]], 1);
    }
    int togo = 0, cnt = 0;
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < m; j++){
            int ans2 = mid.query(1, ord[s[j][i]], near[ord[s[j][i]]], 0, mid.off - 1, 1);
            togo = max(togo, ans2);
        }
        if(togo == i)cnt++, togo++;
    }
    //int dep[N+2], sub[N+2], id[N+2], ord[N+2], near[N+2];
    //vector<int> adj[N+2], order;
    order.clear();
    for(int i = 0; i < n; i++){
        adj[i].clear();
        dep[i] = 0;
        sub[i] = 0;
        ord[i] = 0;
        near[i] = 0;
        id[i] = 0;
    }
    return cnt;
}
// int main(){
//     int tt = 1;
//     //cin>>tt;
//     while(tt--){
//         cout<<solve(3, 1, {-1, 0, 0}, {{1, 2}});
//         cout<<'\n';
//     }
// }

• Subtask 1: 0 / 11
• Subtask 2: 0 / 14
• Subtask 3: 0 / 5
• Subtask 4: 0 / 9
• Subtask 5: 0 / 5
• Subtask 6: 0 / 11
• Subtask 7: 0 / 9
• Subtask 8: 0 / 11
• Subtask 9: 0 / 9
• Subtask 10: 0 / 16