Submission #1108280

#	Time	Username	Problem	Language	Result	Execution time	Memory
1108280		matu	September (APIO24_september)	C++17	0 / 100	2 ms	592 KiB

september

#include <bits/stdc++.h>
// #include <tr2/dynamic_bitset>

using namespace std;
// using namespace tr2;
#pragma GCC optimize("O3,unroll-loops,Ofast")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const long double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int randgen(int left, int right) {
    return uniform_int_distribution<int>(left, right)(rng);
}
long long randgenll(long long left, long long right) {
    return uniform_int_distribution<long long>(left, right)(rng);
}
 
typedef long long ll;
typedef long double ld;
const int mod = 1e9 + 7;
struct Mint
{
    int val;
    Mint(int x = 0)
    {
        val = x % mod;
    }
    Mint(long long x)
    {
        val = x % mod;
    }
    Mint operator+(Mint oth)
    {
        return val + oth.val;
    }
    Mint operator*(Mint oth)
    {
        return 1LL * val * oth.val;
    }
    Mint operator-(Mint oth)
    {
        return val - oth.val + mod;
    }
    Mint fp(Mint a, long long n){
        Mint p = 1;
        while(n){
            if(n & 1){
                p = p * a;
            }
            a = a * a;
            n /= 2;
        }
        return p;
    }
    Mint operator/(Mint oth){
        Mint invers = fp(oth, mod - 2);
        return 1LL * val * invers.val;
    }
    friend ostream& operator << (ostream& os, const Mint& lol){
        os << lol.val;
        return os;
    }
};
 
struct AINT{
    vector<ll> aint;
    vector<ll> lazy;
  
    AINT(int n){
       
        aint.assign(n * 4 + 1,-1e9);
        //lazy.assign(n * 4 + 1, -1);
    }
    void update(int v, int tl, int tr, int pos, int val){
        if(tl == tr){
            aint[v] = val;
            return;
        }
        int tm = (tl + tr) / 2;
        if(pos <= tm) update(v * 2, tl ,tm, pos, val);
        else update(v * 2 + 1, tm + 1, tr, pos,val);
        aint[v] = max(aint[v * 2], aint[v * 2 + 1]);
    }
    int query(int v, int tl, int tr, int l, int r){
        
        int tm = (tl + tr) / 2;
        if(l <= tl && r >= tr) return aint[v];
        if(l > tr || r < tl) return -1e9;
        return max(query(v * 2, tl, tm,l,r), query(v * 2 + 1, tm + 1, tr, l,r));
        
    }
};
struct AIB{
    vector<int> aib;
    AIB(int n){
        aib.assign(n + 1,0);
    
    }
    void update(int pos, int val){
        for(; pos < aib.size(); pos += (pos & -pos)){
            aib[pos] += val;
        }
    }
    int query(int pos){
        int pl = 0;
   
        for(; pos > 0; pos -= (pos & -pos)) pl += aib[pos];
        return pl;
    }
};
 
int red = 0;
 
int ______________________________________________________________________________________________________________________________________________;
 
int solve(int n, int m, vector<int> f, vector<vector<int>> s){
    
    vector<int> nrf(n + 1);
    vector<vector<int>> liste(n + 1);
    for(int i = 1; i < n; i++){
        liste[i].push_back(f[i]);
        liste[f[i]].push_back(i);
    }
    vector<int> leaves(n + 1);
    function<void(int,int)> dfs = [&](int nod, int p){
        for(auto i : liste[nod]){
            if(i == p) continue;
            nrf[nod]++;
            // if(nod == 0){
            //     cout << i << " ";
            // }
            dfs(i,nod);
        }
        if(liste[nod].size() == 1 && nod != 0){
            leaves[nod] = 1;
        }
    }; 
    dfs(0,0);
    map<set<int>,int> mp;
    int ans = 0;
    vector<set<int>> lp(m + 1);
    for(int i = 0; i < n - 1; i++){
       
        for(int l = 0; l < m; l++){
            if(!leaves[s[l][i]]){
                //cout << leaves[s[l][i]] << " ";
                return 1;
            }
            lp[l].insert(s[l][i]);
            mp[lp[l]]++;
            if(mp[lp[l]] == m){

                for(auto k : lp[l]){
                    if(--nrf[f[k]] == 0){
                        leaves[f[k]] = 1;
                    }
                }
                for(int k = 0; k < m; k++){
                    lp[k].clear();
                }
                ans++;
            }
        }
    }
    return ans;
}
// int32_t main(){
//     cin.tie(0)->sync_with_stdio(0);
    
//     // int t = 1; 
//     // if(red) cin >> t;
   
//     // while(t--){
//     //     solve();
//     // }
//     cout << solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4, 1, 2, 3}});
 
 
// }
 
 
/*
 4 1
0 0 1


dp[i][0] = s


*/

Compilation message (stderr)

september.cpp: In member function 'void AIB::update(int, int)':
september.cpp:99:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |         for(; pos < aib.size(); pos += (pos & -pos)){
      |               ~~~~^~~~~~~~~~~~

• 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