Submission #253703

#	Time	Username	Problem	Language	Result	Execution time	Memory
253703		Erkhemkhuu	Split the Attractions (IOI19_split)	C++17	0 / 100	2 ms	2688 KiB

split

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
const ll N = 100005;
vector <ll> path, path1;
bool vis[N];
vector <vector <ll> > adj(N);
ll need1, need2;
void dfs(ll v, ll cur) {
    path.pb(v);
    if(cur == need1 + 1) return;
    vis[v] = true;
    for(auto &u: adj[v]) {
        if(vis[u]) continue;
        dfs(u, cur + 1);
    }
    return;
}
void dfs1(ll v, ll cur) {
    path1.pb(v);
    if(cur == need2 + 1) return;
    vis[v] = true;
    for(auto &u: adj[v]) {
        if(vis[u]) continue;
        dfs1(u, cur + 1);
    }
    return;
}
vector <ll> find_split(int n, int a, int b, int c, vector <int> p, vector <int> q) {
    ll m = p.size(), i;
    for(i = 0; i < m; i++) {
        adj[p[i]].pb(q[i]);
        adj[q[i]].pb(p[i]);
    }
    vector <ll> vc;
    vc = {a, b, c};
    sort(vc.begin(), vc.end());
    need1 = vc[0];
    need2 = vc[1];
    dfs(0, 1);
    for(i = n - 1; i >= 1; i--) {
        if(!vis[i]) {
            dfs1(i, 1);
            break;
        }
    }
    vector <ll> ans(n, 0);
    for(auto &x: path)
        ans[x] = 1;
    for(auto &x: path1)
        ans[x] = 2;
    for(i = 0; i < n; i++)
        if(!vis[i]) ans[i] = 3;
    return ans;
}

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