oj.uz

Submission #911879

# Submission time Handle Problem Language Result Execution time Memory
911879 2024-01-19T06:02:49 Z Sir_Ahmed_Imran Parachute rings (IOI12_rings) C++17
55 / 100
 4000 ms 165888 KB 
                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define all(x) (x).begin(),(x).end()
#define pii pair<int,int>
#define MAXN 1000001
int n,x;
int f[MAXN];
int par[MAXN];
vector<int> a[MAXN];
unordered_map<int,int> e,z,vis;
void dfs(int v,int u,vector<int>& vec){
    vis[v]=1;
    vec.append(v);
    for(auto& i:a[v])
        if(!vis[i])
            dfs(i,u,vec);
    if(vec.back()!=u) vec.pop_back();
}
int root(int v){
    if(par[v]==v) return v;
    par[v]=root(par[v]);
    return par[v];
}
void join(int v,int u){
    v=root(v);
    u=root(u);
    par[u]=v;
    f[v]+=f[u];
}
bool same(int v,int u){
    return (root(v)==root(u));
}
void Init(int u){
    n=x=u;
    for(int i=0;i<n;i++){
        par[i]=i; 
        e[i]=1;
    }
}
void Link(int v, int u){
    if(!x) return;
    if(!f[root(v)] && same(v,u)){
        vector<int> vec;
        dfs(v,u,vec);
        vis.clear();
        x=0;
        for(auto& i:vec){
            if(e[i]){
                x++;
                z[i]=e[i];
            }
        }
        swap(e,z);
        z.clear();
        f[root(v)]==1;
    }
    a[v].append(u);
    a[u].append(v);
    join(v,u);
    if(a[v].size()>3){
        x=e[v];
        e.clear();
        e[v]=x;
    }
    if(a[u].size()>3){
        x=e[u];
        e.clear();
        e[u]=x;
    }
    if(a[v].size()==3){
        x=0;
        if(e[v]){
            x++;
            z[v]=e[v];
        }
        for(auto& i:a[v]){
            if(e[i]){
                x++;
                z[i]=e[i];
            }
        }
        swap(e,z);
        z.clear();
    }
    if(a[u].size()==3){
        x=0;
        if(e[u]){
            x++;
            z[u]=e[u];
        }
        for(auto& i:a[u]){
            if(e[i]){
                x++;
                z[i]=e[i];
            }
        }
        swap(e,z);
        z.clear();
    }
}
int CountCritical(){
    return x;;
}

Compilation message

rings.cpp: In function 'void Link(int, int)':
rings.cpp:61:19: warning: value computed is not used [-Wunused-value]
   61 |         f[root(v)]==1;
      |         ~~~~~~~~~~^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 8 ms 25436 KB Output is correct
3 Correct 10 ms 25704 KB Output is correct
4 Correct 8 ms 25180 KB Output is correct
5 Correct 9 ms 25692 KB Output is correct
6 Correct 12 ms 25948 KB Output is correct
7 Correct 8 ms 25480 KB Output is correct
8 Correct 9 ms 25436 KB Output is correct
9 Correct 9 ms 25612 KB Output is correct
10 Correct 11 ms 25432 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 380 ms 67292 KB Output is correct
2 Correct 818 ms 80500 KB Output is correct
3 Correct 213 ms 74728 KB Output is correct
4 Correct 1016 ms 105600 KB Output is correct
5 Correct 960 ms 107944 KB Output is correct
6 Correct 1593 ms 165888 KB Output is correct
7 Correct 209 ms 74752 KB Output is correct
8 Correct 879 ms 98276 KB Output is correct
9 Correct 983 ms 104468 KB Output is correct
10 Correct 725 ms 104096 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 8 ms 25436 KB Output is correct
3 Correct 10 ms 25704 KB Output is correct
4 Correct 8 ms 25180 KB Output is correct
5 Correct 9 ms 25692 KB Output is correct
6 Correct 12 ms 25948 KB Output is correct
7 Correct 8 ms 25480 KB Output is correct
8 Correct 9 ms 25436 KB Output is correct
9 Correct 9 ms 25612 KB Output is correct
10 Correct 11 ms 25432 KB Output is correct
11 Correct 8 ms 25436 KB Output is correct
12 Correct 12 ms 25988 KB Output is correct
13 Correct 10 ms 25692 KB Output is correct
14 Correct 411 ms 25692 KB Output is correct
15 Correct 617 ms 26020 KB Output is correct
16 Correct 12 ms 26020 KB Output is correct
17 Correct 12 ms 25692 KB Output is correct
18 Correct 10 ms 26200 KB Output is correct
19 Correct 11 ms 25944 KB Output is correct
20 Correct 11 ms 26200 KB Output is correct

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 8 ms 25436 KB Output is correct
3 Correct 10 ms 25704 KB Output is correct
4 Correct 8 ms 25180 KB Output is correct
5 Correct 9 ms 25692 KB Output is correct
6 Correct 12 ms 25948 KB Output is correct
7 Correct 8 ms 25480 KB Output is correct
8 Correct 9 ms 25436 KB Output is correct
9 Correct 9 ms 25612 KB Output is correct
10 Correct 11 ms 25432 KB Output is correct
11 Correct 8 ms 25436 KB Output is correct
12 Correct 12 ms 25988 KB Output is correct
13 Correct 10 ms 25692 KB Output is correct
14 Correct 411 ms 25692 KB Output is correct
15 Correct 617 ms 26020 KB Output is correct
16 Correct 12 ms 26020 KB Output is correct
17 Correct 12 ms 25692 KB Output is correct
18 Correct 10 ms 26200 KB Output is correct
19 Correct 11 ms 25944 KB Output is correct
20 Correct 11 ms 26200 KB Output is correct
21 Correct 24 ms 28520 KB Output is correct
22 Correct 43 ms 30308 KB Output is correct
23 Correct 49 ms 32200 KB Output is correct
24 Execution timed out 4026 ms 30172 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 25180 KB Output is correct
2 Correct 8 ms 25436 KB Output is correct
3 Correct 10 ms 25704 KB Output is correct
4 Correct 8 ms 25180 KB Output is correct
5 Correct 9 ms 25692 KB Output is correct
6 Correct 12 ms 25948 KB Output is correct
7 Correct 8 ms 25480 KB Output is correct
8 Correct 9 ms 25436 KB Output is correct
9 Correct 9 ms 25612 KB Output is correct
10 Correct 11 ms 25432 KB Output is correct
11 Correct 380 ms 67292 KB Output is correct
12 Correct 818 ms 80500 KB Output is correct
13 Correct 213 ms 74728 KB Output is correct
14 Correct 1016 ms 105600 KB Output is correct
15 Correct 960 ms 107944 KB Output is correct
16 Correct 1593 ms 165888 KB Output is correct
17 Correct 209 ms 74752 KB Output is correct
18 Correct 879 ms 98276 KB Output is correct
19 Correct 983 ms 104468 KB Output is correct
20 Correct 725 ms 104096 KB Output is correct
21 Correct 8 ms 25436 KB Output is correct
22 Correct 12 ms 25988 KB Output is correct
23 Correct 10 ms 25692 KB Output is correct
24 Correct 411 ms 25692 KB Output is correct
25 Correct 617 ms 26020 KB Output is correct
26 Correct 12 ms 26020 KB Output is correct
27 Correct 12 ms 25692 KB Output is correct
28 Correct 10 ms 26200 KB Output is correct
29 Correct 11 ms 25944 KB Output is correct
30 Correct 11 ms 26200 KB Output is correct
31 Correct 24 ms 28520 KB Output is correct
32 Correct 43 ms 30308 KB Output is correct
33 Correct 49 ms 32200 KB Output is correct
34 Execution timed out 4026 ms 30172 KB Time limit exceeded
35 Halted 0 ms 0 KB -