Submission #1288064

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288064		al95ireyiz	Split the Attractions (IOI19_split)	C++20	0 / 100	1 ms	428 KiB

split

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e9, INFL = 1e18;
const ll MOD = 1e9 + 7;
const ll maxn = 1e5 + 5;

ll n, m, k = 0;

#include "split.h"

vector<ll> g[maxn];
pair<vector<ll>, vector<ll>>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)

    // demeli biz ele u - v cutu tapmaliyiq ki,
    // 1) u ve v arasinda edge olsun;
    // 2) bu edge-i silende v -nin subtree size-i >= a olsun ve u -nun subtree size-i >= b olsun;
    // ** Esas Observation(+60 pts): tree olmayan qraf ucun ise, spanning tree mentiqi ile tree-ye cevire bilerik.
    
    // UNFINISHED
}
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 < _p.size(); i ++){
        g[_p[i]].push_back(_q[i]), g[_q[i]].push_back(_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(ax.size() != _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(ax.size() != _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(bx.size() != _b) return cv;
        cv.assign(n, 1);
        for(auto i : bx) cv[i] = 2;
        for(auto i : cx) cv[i] = 3;
    }
    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";
// }

Compilation message (stderr)

split.cpp: In function 'std::pair<std::vector<long long int>, std::vector<long long int> > f(long long int, long long int)':
split.cpp:27:1: warning: no return statement in function returning non-void [-Wreturn-type]
   27 | }
      | ^

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36