Submission #1042614

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042614		idas	Split the Attractions (IOI19_split)	C++17	18 / 100	59 ms	13108 KiB

split

#include "split.h"
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back

using namespace std;
typedef vector<int> vi;

const int MxN=1e5+10;
int n, m, dp[MxN], s[3], re[MxN], idx;
vi ad[MxN];

bool v[MxN];
void dfs(int u)
{
    re[idx++]=u;
    v[u]=true;
    for(auto it : ad[u]){
        if(v[it]) continue;
        dfs(it);
    }
}

vector<int> find_split(int N, int a, int b, int c, vector<int> p, vector<int> q) {
    n=N; m=p.size();

    vi cn(n);
    FOR(i, 0, m)
    {
        ad[p[i]].pb(q[i]);
        ad[q[i]].pb(p[i]);
        cn[p[i]]++; cn[q[i]]++;
    }

    bool fnd=false;
    FOR(i, 0, n)
    {
        if(cn[i]==1){
            dfs(i);
            fnd=true;
            break;
        }
    }

    if(!fnd) dfs(0);

    vi ans(n);
    FOR(i, 0, a) ans[re[i]]=1;
    FOR(i, a, a+b) ans[re[i]]=2;
    FOR(i, a+b, a+b+c) ans[re[i]]=3;

//    vi tmp; tmp.pb(a); tmp.pb(b); tmp.pb(c);
//    //sort(tmp.begin(), tmp.end());
//    FOR(z, 0, 3) s[z]=tmp[z];
//
//    FOR(i, 0, m) {
//        ad[p[i]].pb(q[i]);
//        ad[q[i]].pb(p[i]);
//    }
//    pre(0);
//    dfs(0);
//
//    FOR(i, 0, n) ans.pb(0);
//    if(x==-1) return ans;
//
//    FOR(i, 0, n) ans[i]=3;
//
//    spread(x, 0, y);
//    spread(y, 1, x);
//
////    cout << x << " " << y << ": " << rev << endl;
////    cout << s[0] << " " << s[1] << endl;

    return ans;
}

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