Submission #298742

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

split

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
using vi = vector<int>;
using ii = pair<int,int>;

const int MAXN=100000;
int V,E;
ii sizes[3];
vi adj[MAXN];
vi ans;
int vis[MAXN];
int p[MAXN];
bool cycle;

void dfs(int u) {
    vis[u] = 1;
    for (int v : adj[u]) {
        if (!vis[v]) {
            p[v] = u;
            dfs(v);
        } else if (v != p[u] && vis[v]) {
            cycle = true;
        }
    }
}

void resetVis() {
    for (int i=0; i<V; i++) {
        vis[i] = 0;
    }
}

vi find_split(int _V, int a, int b, int c, vi _u, vi _v) {
    /// Init global state
    int E = _u.size();
    V = _V;
    for (int i=0; i<E; i++) {
        int a = _u[i];
        int b = _v[i];
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    sizes[0] = {a,1};
    sizes[1] = {b,2};
    sizes[2] = {c,3};
    sort(sizes, sizes+3);
    ans.resize(V);
    /// Actual implementation
    if (sizes[0].first + sizes[1].first <= V) {
        resetVis();
        dfs(0);
        int u;
        if (cycle) {
            resetVis();
            u = 0;
        } else {
            for (int i=0; i<V; i++) {
                if (adj[i].size() == 1) {
                    u = i;
                    break;
                }
            }
        }
        resetVis();
        for (int s=0; s<2; s++) {
            for (int i=0; i<sizes[s].first; i++) {
                ans[i] = sizes[s].second;
                vis[u] = true;
                for (int v : adj[u]) {
                    if (!vis[u]) {
                        u = v;
                        break;
                    }
                }
            }
        }
    }
    return ans;
}

// int main() {
//     int n,m,a,b,c;
//     cin>>n>>m;
//     cin>>a>>b>>c;
//     vi u(m);
//     vi v(m);
//     for (int i=0; i<m; i++) {
//         cin>>u[i]>>v[i];        
//     }
//     vi ans = find_split(n,a,b,c,u,v);
//     for (int i : ans) {
//         cout<<i<<' ';
//     }
//     cout<<'\n';
// }

Compilation message (stderr)

split.cpp: In function 'vi find_split(int, int, int, int, vi, vi)':
split.cpp:71:24: warning: 'u' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |                 vis[u] = true;
      |                 ~~~~~~~^~~~~~

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