Submission #1194954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1194954		Aestivate	September (APIO24_september)	C++20	0 / 100	1095 ms	320 KiB

september

#include<bits/stdc++.h>
using namespace std;
#define pb push_back

vector<vector<int>>node;
int tot;
vector<int>ne;

void go(int v){
    if(ne[v]) return;
    tot++;
    ne[v]=1;
    for(int g: node[v]){
        go(g);
    }
}

int solve(int n, int m, vector<int>f, vector<vector<int>>s){
    tot=0;
    ne=vector<int>(n+1, 0);
    for(int i=0;i<n;i++) node.emplace_back();
    // cerr<<node.size()<<"\n";
    // cerr<<n<<" "<<node.size()<<" "<<ne.size()<<"\n";
    for(int i=1;i<n;i++){
        node[f[i]].pb(i);
    }
    int now=0;
    int ans=0;
    vector<int>vis(n+1, 0);
    while(now<n-1){
        for(int i=0;i<s.size();i++){
            if(vis[s[i][now]] == 0) go(s[i][now]);
            if(vis[s[i][now]] == 0) tot--;
            vis[s[i][now]]=1;
        }
        now++;
        bool ok=0;
        while(!ok||tot){
            if(now==n-1) break;
            bool ok2=1;
            for(int i=0;i<s.size();i++){
                if(vis[s[i][now]]){
                    ok2=0;
                }
            }
            if(!ok2){
                for(int i=0;i<s.size();i++){
                    if(vis[s[i][now]]==0) go(s[i][now]);
                    if(vis[s[i][now]] == 0) tot--;
                    vis[s[i][now]]=1;
                }
                now++;
                ok=0;
            }
            else ok=1;
        }
        ans++;
    }
    node.clear();
    ne.clear();
    return ans;
}

// int main(){
//     int t;
//     cin>>t;
//     while(t--)
//         cout<<solve(5, 2, {-1, 0, 0, 1, 1}, {{1, 2, 3, 4}, {4,  1, 2, 3}})<<" "<<solve(3, 1, {-1, 0, 0}, {{1, 2}})<<"\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