oj.uz

Submission #739482

# Submission time Handle Problem Language Result Execution time Memory
739482 2023-05-10T14:10:14 Z vjudge1 Stove (JOI18_stove) C++17
100 / 100
 62 ms 85056 KB 
#include <bits/stdc++.h>
#include <math.h>
//in the name of god,aka allah
//** har vaght m2 ghabool shodi javabetoo midam (radal) **
#pragma GCC optimize("unroll-loops")
using namespace std;
#define pi pair<ll , ll>
#define pii pair<long long , pair<long long , long long>>
const int maxm = 5e5 + 6;
const long long mod = 998244353;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
ll l,r,mid;
ll n,m;
ll dis[maxm] , sum[maxm];
bool isval(int mid){
    //cout << mid <<" " << mid*mid-mid <<endl;
    if (((mid-1)*mid)/2 < m) return 0;
    return 1;
}
ll darage[maxm] , ss , mm;
queue<int> q;
vector<ll> g[maxm] , z[maxm];
ll sath[maxm];
bool vis[maxm] , gos[maxm];
ll pedaret[maxm];
ll get_par(ll v){
    if (pedaret[v]==v) return v;
    return pedaret[v] = get_par(pedaret[v]);
}
void merge(ll r , ll q){
    if (get_par(r)!=get_par(q))l+=max(darage[r],darage[q])*1ll*sath[r]*1ll*sath[q];
    r = get_par(r) , q = get_par(q);
    if (r!=q){
        if (sath[r]<sath[q]) swap(r,q);
        pedaret[q] = r;
        sath[r] += sath[q];
    }
    return ;
}
ll pars1[maxm] , pars2[maxm];
vector<ll> se[maxm];
set<ll> st , wtf , ajab;
ll dp[maxm];
ll rp[maxm];
pi w[maxm],ww[maxm];
//ll rw[maxm][maxm];
set<ll> ts[maxm] , jav[maxm];
ll rgh[maxm] , lft[maxm];
ll pw(ll x , ll y){
    ll ans = 1 , ok = x;
    while (y){
        if (y%2) ans *= ok;
        ans %= mod;
        ok *= ok;
        ok %= mod;
        y/=2;
    }
    return ans;
}
ll solve(ll x){
    for (int i=1; i<=n; i++) vis[i] = 0 , darage[i] = mod , gos[i] = 0;
    ll ans = 1;
    queue<int> qu;
    qu.push(x);
    darage[x] = 1;
    ll tr = 0;
    vis[x] = 1;
    while (qu.size()){
        auto x = qu.front();
        qu.pop();
        for (auto u : g[x]){
            if (!vis[u]){
                vis[u] = 1 , darage[u] = darage[x] + 1 , gos[x] = 1 , qu.push(u) , ans++;
            }
        }
    }
    for (int i=1; i<=n; i++) tr += darage[i];
    if (ans!=n) return mod*mod;
    return tr;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >>n>>m;
    l = n;
    for (int i=1; i<=n; i++) cin>>pedaret[i] , darage[i-1] = pedaret[i] - pedaret[i-1] - 1;
    sort(darage+1,darage+n);
    for (int i=1; i<=n-m; i++) l+=darage[i];
    cout<<l<<endl;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 82508 KB Output is correct
2 Correct 40 ms 82528 KB Output is correct
3 Correct 39 ms 82480 KB Output is correct
4 Correct 38 ms 82480 KB Output is correct
5 Correct 40 ms 82440 KB Output is correct
6 Correct 39 ms 82508 KB Output is correct
7 Correct 39 ms 82496 KB Output is correct
8 Correct 43 ms 82416 KB Output is correct
9 Correct 38 ms 82520 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 82508 KB Output is correct
2 Correct 40 ms 82528 KB Output is correct
3 Correct 39 ms 82480 KB Output is correct
4 Correct 38 ms 82480 KB Output is correct
5 Correct 40 ms 82440 KB Output is correct
6 Correct 39 ms 82508 KB Output is correct
7 Correct 39 ms 82496 KB Output is correct
8 Correct 43 ms 82416 KB Output is correct
9 Correct 38 ms 82520 KB Output is correct
10 Correct 40 ms 82552 KB Output is correct
11 Correct 40 ms 82564 KB Output is correct
12 Correct 42 ms 82508 KB Output is correct
13 Correct 40 ms 82620 KB Output is correct
14 Correct 41 ms 82516 KB Output is correct
15 Correct 40 ms 82548 KB Output is correct

Subtask #3
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 82508 KB Output is correct
2 Correct 40 ms 82528 KB Output is correct
3 Correct 39 ms 82480 KB Output is correct
4 Correct 38 ms 82480 KB Output is correct
5 Correct 40 ms 82440 KB Output is correct
6 Correct 39 ms 82508 KB Output is correct
7 Correct 39 ms 82496 KB Output is correct
8 Correct 43 ms 82416 KB Output is correct
9 Correct 38 ms 82520 KB Output is correct
10 Correct 40 ms 82552 KB Output is correct
11 Correct 40 ms 82564 KB Output is correct
12 Correct 42 ms 82508 KB Output is correct
13 Correct 40 ms 82620 KB Output is correct
14 Correct 41 ms 82516 KB Output is correct
15 Correct 40 ms 82548 KB Output is correct
16 Correct 58 ms 84948 KB Output is correct
17 Correct 55 ms 84992 KB Output is correct
18 Correct 62 ms 84956 KB Output is correct
19 Correct 58 ms 85056 KB Output is correct
20 Correct 55 ms 84940 KB Output is correct
21 Correct 56 ms 84996 KB Output is correct
22 Correct 56 ms 84980 KB Output is correct
23 Correct 55 ms 84968 KB Output is correct
24 Correct 58 ms 84992 KB Output is correct