제출 #1287064

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287064		al95ireyiz	사이버랜드 (APIO23_cyberland)	C++20	0 / 100	26 ms	8764 KiB

cyberland

#pragma GCC optimize("O3", "fast-math", "unroll-loops", "no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
#if !defined(ONLINE_JUDGE) and !defined(EVAL)
#include "template/debug.h"
#else
#define d(x...)
#endif
#define fr first
#define er erase
#define in insert
#define sc second
#define ll long long
#define pb push_back
#define vll vector<ll>
#define pll pair<ll,ll>
#define len(x) (ll) x.size()
#define all(x) x.begin(),x.end()
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll maxn = 1e5 + 5;

ll n, m, k = 0;

// A suali
// #include "split.h"
// mt19937 rng(clock());
// vll g[maxn];
// pair<vll, vll>f(ll a, ll b){
//     if(a > b) swap(a, b);
//     // 7 balliq subtask : cycle (AC)
//     // 11 balliq subtask : a = 1 (AC)
//     // 22 balliq subtask : tree (AC)
// }
// vector<int> find_split(int _n, int _a, int _b, int _c, vector<int> p, vector<int> q) {
//     n = _n;
//     for(ll i = 0; i < n; i ++) g[i].clear();
//     for(ll i = 0; i < len(p); i ++){
//         g[p[i]].pb(q[i]), g[q[i]].pb(p[i]);
//     }
//     vector<int>cv(n);
//     if(_a <= _c and _b <= _c){
//         auto [ax, bx] = f(_a, _b);
//         if(_a > _b) swap(ax, bx);
//         if(len(ax) != _a) return cv;
//         cv.assign(n, 3);
//         for(auto i : ax) cv[i] = 1;
//         for(auto i : bx) cv[i] = 2;
//     }
//     else if(_a <= _b and _c <= _b){
//         auto [ax, cx] = f(_a, _c);
//         if(_a > _c) swap(ax, cx);
//         if(len(ax) != _a) return cv;
//         cv.assign(n, 2);
//         for(auto i : ax) cv[i] = 1;
//         for(auto i : cx) cv[i] = 3;
//     }
//     else{
//         auto [bx, cx] = f(_b, _c);
//         if(_b > _c) swap(bx, cx);
//         if(len(bx) != _b) return cv;
//         cv.assign(n, 1);
//         for(auto i : bx) cv[i] = 2;
//         for(auto i : cx) cv[i] = 3;
//     }
//     return cv;
// }

// B suali
// Skipledim helelik

// C suali
// Observation: k = min(k, 30) olmagi besdi cunki ondan boyuk olanda menasi olmur(x <= 2^30)

vector<pll>g[maxn];
ll en, a[maxn], vis[maxn], p[maxn];
void dfs(ll u){
    vis[u] = 1;
    for(auto [v, w] : g[u]){
        if(vis[v]) continue;
        p[v] = u;
        dfs(v);
    }
}
double solve(int N, int M, int K, int H, std::vector<int> x, std::vector<int> y, std::vector<int> c, std::vector<int> arr){
    n = N, m = M, k = K, en = H;
    k = min(k, 30ll); // Observation 1 (line 74)
    for(ll i = 0; i < len(x); i ++){
        g[x[i]].pb({y[i], c[i]});
        g[y[i]].pb({x[i], c[i]});
    }
    for(ll i = 0; i < n; i ++){
        a[i] = arr[i];
    }
    // tree olan subtasklar:
    // onsuz treedi deye 1 dene yol var ona gore o yolu qurub sonra hardasa 0 varsa hemise onu isletmek mentiqlidi
    // 2-lerden ise k denesini cyberlanda yaxinlasan yerlerden secmek mentiqlidi
    dfs(en);
    d(1);
    vll v;
    // for(ll i = 0; i != en; i = p[i]) v.pb(i);
    // v.pb(en);
    reverse(all(v));
    double cv = 0, p = 1;
    auto get = [&](ll x, ll y){
        for(auto [v, w] : g[x]) if(v == y) return w;
    };
    ll say = 0;
    for(ll i = 0; i < len(v); i ++){
        if(a[v[i]] == 0) break;
        if(a[v[i]] == 2) say ++;
    }
    say = min(say, k);
    while(say --) p *= 2;
    for(ll i = 1; i < len(v); i ++){
        cv += get(v[i], v[i - 1]) / p;
        if(a[v[i]] == 0) break;
        if(a[v[i]] == 2) p /= 2;
    }
    return cv;
}
// void _() {

// }
// signed main() {
//     ll tm = clock();
//     cin.tie(0)->sync_with_stdio(0);
//     ll t = 1;
//     // cin >> t;
//     for(ll tt = 1; tt <= t; tt ++) _();
//     cerr << "\n\033[1;31mTime: \033[1;30m" \
//         << (double)(clock()-tm)/1000000 << "\033[1;32m seconds\n";
// }

컴파일 시 표준 에러 (stderr) 메시지

cyberland.cpp: In lambda function:
cyberland.cpp:108:5: warning: control reaches end of non-void function [-Wreturn-type]
  108 |     };
      |     ^

• Subtask 1: 0 / 5
• Subtask 2: 0 / 8
• Subtask 3: 0 / 13
• Subtask 4: 0 / 19
• Subtask 5: 0 / 7
• Subtask 6: 0 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3