oj.uz

Submission #1009072

# Submission time Handle Problem Language Result Execution time Memory
1009072 2024-06-27T08:33:04 Z erering Parachute rings (IOI12_rings) C++17
20 / 100
 4000 ms 41040 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define ll long long
const long long inf=1e18;
const int MOD=998244353;
const int N=1e6+5;
vector<int> adj[N];
int n;
bool vis[N];
struct info{
    int one;
    int mx;
};
info dfs(int node,int par,int kr){
    vis[node]=1;
    info rt; rt.one=0; rt.mx=0;
    int bad=0;
    for(auto i:adj[node]){
        if(i!=kr)bad++;
        if(vis[i])continue;
        info s=dfs(i,node,kr);
        rt.one+=s.one;
        rt.mx=max(rt.mx,s.mx);
    }
    if(bad==1)rt.one+=1;
    rt.mx=max(rt.mx,bad);
    return rt;
}
void Init(int N){
    n=N;
}
void Link(int A, int B){
    A++; B++;
    adj[A].pb(B);
    adj[B].pb(A);
}
int CountCritical(){
    for(int i=1;i<=n;i++)vis[i]=0;
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)vis[j]=0;
        vis[i]=1;
        bool flag=1;
        for(int j=1;j<=n;j++){
            if(!vis[j]){
                info yes=dfs(j,0,i);
                if(yes.mx==0)continue;
                if(yes.mx>=3 || yes.one!=2)flag=0;
            }
        }
        if(flag){
            ans++;
        }
    }
    return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24668 KB Output is correct
2 Correct 214 ms 24668 KB Output is correct
3 Correct 360 ms 24156 KB Output is correct
4 Correct 15 ms 24664 KB Output is correct
5 Correct 111 ms 24964 KB Output is correct
6 Correct 341 ms 25224 KB Output is correct
7 Correct 90 ms 24664 KB Output is correct
8 Correct 225 ms 24920 KB Output is correct
9 Correct 297 ms 24920 KB Output is correct
10 Correct 272 ms 24920 KB Output is correct

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4088 ms 41040 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24668 KB Output is correct
2 Correct 214 ms 24668 KB Output is correct
3 Correct 360 ms 24156 KB Output is correct
4 Correct 15 ms 24664 KB Output is correct
5 Correct 111 ms 24964 KB Output is correct
6 Correct 341 ms 25224 KB Output is correct
7 Correct 90 ms 24664 KB Output is correct
8 Correct 225 ms 24920 KB Output is correct
9 Correct 297 ms 24920 KB Output is correct
10 Correct 272 ms 24920 KB Output is correct
11 Execution timed out 4056 ms 24916 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24668 KB Output is correct
2 Correct 214 ms 24668 KB Output is correct
3 Correct 360 ms 24156 KB Output is correct
4 Correct 15 ms 24664 KB Output is correct
5 Correct 111 ms 24964 KB Output is correct
6 Correct 341 ms 25224 KB Output is correct
7 Correct 90 ms 24664 KB Output is correct
8 Correct 225 ms 24920 KB Output is correct
9 Correct 297 ms 24920 KB Output is correct
10 Correct 272 ms 24920 KB Output is correct
11 Execution timed out 4056 ms 24916 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 24668 KB Output is correct
2 Correct 214 ms 24668 KB Output is correct
3 Correct 360 ms 24156 KB Output is correct
4 Correct 15 ms 24664 KB Output is correct
5 Correct 111 ms 24964 KB Output is correct
6 Correct 341 ms 25224 KB Output is correct
7 Correct 90 ms 24664 KB Output is correct
8 Correct 225 ms 24920 KB Output is correct
9 Correct 297 ms 24920 KB Output is correct
10 Correct 272 ms 24920 KB Output is correct
11 Execution timed out 4088 ms 41040 KB Time limit exceeded
12 Halted 0 ms 0 KB -