Submission #291094

#	Time	Username	Problem	Language	Result	Execution time	Memory
291094		alexandra_udristoiu	Split the Attractions (IOI19_split)	C++14	100 / 100	176 ms	17784 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){
        sol[nod] = ind;
        s++;
    }
    else{
        return;
    }
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(t[vecin] == nod){
            dfs2(vecin, ind, s, nr);
        }
    }
}
static void dfs3(int nod, int ind, int &s, int nr){
    if(s < nr){
        sol[nod] = ind;
        s++;
    }
    else{
        return;
    }
    for(int i = 0; i < v[nod].size(); i++){
        int vecin = v[nod][i];
        if(sol[vecin] == 0){
            dfs3(vecin, 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, jj;
    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]);
    }
    t[0] = -1;
    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 = 1;
            sb = 0;
            sol[i] = ind[1];
            for(jj = 0; jj < v[i].size(); jj++){
                nod = v[i][jj];
                if(t[nod] == i){
                    if(jj >= j || e[nod] >= niv[i]){
                        dfs2(nod, ind[1], sa, a);
                    }
                }
            }
            dfs3(t[i], 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){
            sb = 1;
            sa = 0;
            sol[i] = ind[2];
            for(jj = 0; jj < v[i].size(); jj++){
                nod = v[i][jj];
                if(t[nod] == i){
                    if(jj >= j || e[nod] >= niv[i]){
                        dfs2(nod, ind[2], sb, b);
                    }
                }
            }
            dfs3(t[i], ind[1], sa, a);
        }
    }
    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 'void dfs3(int, int, int&, int)':
split.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     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:73:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(i = 0; i < p.size(); i++){
      |                ~~^~~~~~~~~~
split.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
split.cpp:97:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for(jj = 0; jj < v[i].size(); jj++){
      |                         ~~~^~~~~~~~~~~~~
split.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(j = 0; j < v[i].size(); j++){
      |                    ~~^~~~~~~~~~~~~
split.cpp:124:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             for(jj = 0; jj < v[i].size(); jj++){
      |                         ~~~^~~~~~~~~~~~~

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