oj.uz

Submission #290940

# Submission time Handle Problem Language Result Execution time Memory
290940 2020-09-04T14:54:39 Z alexandra_udristoiu Split the Attractions (IOI19_split) C++14
18 / 100
 142 ms 14968 KB 
#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[1], sa, a);
            }
        }
    }
    if(ok == 1){
        for(i = 0; i < n; i++){
            if(sol[i] == 0){
                sol[i] = ind[3];
            }
        }
    }
    return sol;
}

Compilation message

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 105 ms 14584 KB ok, correct split
8 Correct 93 ms 13176 KB ok, correct split
9 Correct 98 ms 12792 KB ok, correct split
10 Correct 95 ms 14712 KB ok, correct split
11 Correct 106 ms 14712 KB ok, correct split

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 118 ms 13360 KB ok, correct split
5 Correct 88 ms 10232 KB ok, correct split
6 Correct 96 ms 14968 KB ok, correct split
7 Correct 103 ms 13176 KB ok, correct split
8 Correct 142 ms 12536 KB ok, correct split
9 Correct 96 ms 10232 KB ok, correct split
10 Correct 62 ms 10608 KB ok, correct split
11 Correct 64 ms 10480 KB ok, correct split
12 Correct 64 ms 10480 KB ok, correct split

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Incorrect 90 ms 10232 KB invalid split: #1=1, #2=40000, #3=59999
3 Halted 0 ms 0 KB -

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, no valid answer
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 2 ms 2688 KB ok, correct split
8 Correct 2 ms 2688 KB ok, correct split
9 Correct 4 ms 2944 KB ok, correct split
10 Correct 4 ms 2944 KB ok, correct split
11 Correct 2 ms 2688 KB ok, correct split
12 Correct 4 ms 2944 KB ok, correct split
13 Correct 2 ms 2688 KB ok, correct split
14 Correct 2 ms 2688 KB ok, correct split
15 Correct 2 ms 2688 KB ok, correct split
16 Correct 2 ms 2688 KB ok, correct split
17 Correct 2 ms 2688 KB ok, correct split
18 Correct 2 ms 2688 KB ok, correct split
19 Correct 2 ms 2688 KB ok, correct split
20 Correct 2 ms 2816 KB ok, correct split
21 Correct 3 ms 2944 KB ok, correct split
22 Incorrect 4 ms 2816 KB invalid split: #1=1, #2=850, #3=1649
23 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB ok, correct split
2 Correct 2 ms 2688 KB ok, correct split
3 Correct 2 ms 2688 KB ok, correct split
4 Correct 2 ms 2688 KB ok, correct split
5 Correct 2 ms 2688 KB ok, correct split
6 Correct 2 ms 2688 KB ok, correct split
7 Correct 105 ms 14584 KB ok, correct split
8 Correct 93 ms 13176 KB ok, correct split
9 Correct 98 ms 12792 KB ok, correct split
10 Correct 95 ms 14712 KB ok, correct split
11 Correct 106 ms 14712 KB ok, correct split
12 Correct 2 ms 2688 KB ok, correct split
13 Correct 2 ms 2688 KB ok, correct split
14 Correct 2 ms 2688 KB ok, correct split
15 Correct 118 ms 13360 KB ok, correct split
16 Correct 88 ms 10232 KB ok, correct split
17 Correct 96 ms 14968 KB ok, correct split
18 Correct 103 ms 13176 KB ok, correct split
19 Correct 142 ms 12536 KB ok, correct split
20 Correct 96 ms 10232 KB ok, correct split
21 Correct 62 ms 10608 KB ok, correct split
22 Correct 64 ms 10480 KB ok, correct split
23 Correct 64 ms 10480 KB ok, correct split
24 Correct 2 ms 2688 KB ok, correct split
25 Incorrect 90 ms 10232 KB invalid split: #1=1, #2=40000, #3=59999
26 Halted 0 ms 0 KB -