Submission #290939

#	Time	Username	Problem	Language	Result	Execution time	Memory
290939		alexandra_udristoiu	Split the Attractions (IOI19_split)	C++14	18 / 100	137 ms	14940 KiB

split

#include "split.h"
#include<vector>
#define DIM 100005
using namespace std;
static int viz[DIM], t[DIM], ind[5], d[DIM], e[DIM], niv[DIM];
static vector<int> v[DIM], sol;
static void dfs(int nod){
    d[nod] = 1;
    e[nod] = niv[nod];
    viz[nod] = 1;
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(viz[vecin] == 0){
            niv[vecin] = niv[nod] + 1;
            t[vecin] = nod;
            dfs(vecin);
            d[nod] += d[vecin];
            e[nod] = min(e[nod], e[vecin]);
        }
        else if(vecin != t[nod]){
            e[nod] = min(e[nod], niv[vecin]);
        }
    }
}
static void dfs2(int nod, int ind, int &s, int nr){
    if(s < nr){
        s++;
        sol[nod] = ind;
    }
    else{
        return;
    }
    for(int i = 0; i < v[nod].size(); i++){
        if(sol[ v[nod][i] ] == 0 && t[ v[nod][i] ] == nod){
            dfs2(v[nod][i], ind, s, nr);
        }
    }
}

vector<int> find_split(int n, int a, int b, int c, vector<int> p, vector<int> q) {
    int i, j, sum, ok, sa, sb, nod;
    ind[1] = 1;
    ind[2] = 2;
    ind[3] = 3;
    if(a > b){
        swap(a, b);
        swap(ind[1], ind[2]);
    }
    if(a > c){
        swap(a, c);
        swap(ind[1], ind[3]);
    }
    if(b > c){
        swap(b, c);
        swap(ind[2], ind[3]);
    }
    for(i = 0; i < p.size(); i++){
        v[ p[i] ].push_back(q[i]);
        v[ q[i] ].push_back(p[i]);
    }
    dfs(0);
    ok = 0;
    sol.resize(n);
    for(i = 1; i < n && ok == 0; i++){
        sum = d[i];
        for(j = 0; j < v[i].size(); j++){
            if(sum >= a && n - sum >= b){
                ok = 1;
                break;
            }
            nod = v[i][j];
            if(t[nod] == i && e[nod] < niv[i]){
                sum -= d[nod];
            }
        }
        if(ok == 1){
            sa = sb = 0;
            sol[i] = ind[1];
            sol[ t[i] ] = ind[2];
            for(j = j - 1; j >= 0; j--){
                 nod = v[i][j];
                if(t[nod] == i && e[nod] < niv[i]){
                    dfs2(nod, ind[2], sb, b);
                }
            }
            dfs2(i, ind[1], sa, a);
            for(j = t[i]; sb < b; j = t[j]){
                dfs2(j, ind[2], sb, b);
            }
            continue;
        }

        sum = d[i];
        for(j = 0; j < v[i].size(); j++){
            if(sum >= b && n - sum >= a){
                ok = 1;
                break;
            }
            nod = v[i][j];
            if(t[nod] == i && e[nod] < niv[i]){
                sum -= d[nod];
            }
        }
        if(ok == 1){
            sa = sb = 0;
            sol[i] = ind[2];
            sol[ t[i] ] = ind[1];
            for(j = j - 1; j >= 0; j--){
                 nod = v[i][j];
                if(t[nod] == i && e[nod] < niv[i]){
                    dfs2(nod, ind[1], sa, a);
                }
            }
            dfs2(i, ind[2], sb, b);
            for(j = t[i]; sb < b; j = t[j]){
                dfs2(j, ind[2], sb, b);
            }
        }
    }
    if(ok == 1){
        for(i = 0; i < n; i++){
            if(sol[i] == 0){
                sol[i] = ind[3];
            }
        }
    }
    return sol;
}

Compilation message (stderr)

split.cpp: In function 'void dfs(int)':
split.cpp:11:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
split.cpp: In function 'void dfs2(int, int, int&, int)':
split.cpp:33:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     for(int i = 0; i < v[nod].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:57:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(i = 0; i < p.size(); i++){
      |                ~~^~~~~~~~~~
split.cpp:66:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
split.cpp:94:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~

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