oj.uz

Submission #238783

# Submission time Handle Problem Language Result Execution time Memory
238783 2020-06-12T21:42:48 Z duality Split the Attractions (IOI19_split) C++14
46 / 100
 168 ms 43640 KB 
#define DEBUG 0

#include <bits/stdc++.h>
using namespace std;

#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}

// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
    public:
        template<typename T>
        _Debug& operator,(T val) {
            cout << val << endl;
            return *this;
        }
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif

// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back

// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;

// ---------- END OF TEMPLATE ----------

vi adjList[100000],adjList2[100000];
int parent[100000],size[100000],disc[100000],low[100000],fin[100000],num = 0;
int doDFS(int u,int p) {
    int i;
    parent[u] = p,size[u] = 1,disc[u] = low[u] = num++;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (disc[v] == -1) {
            adjList2[u].pb(v),size[u] += doDFS(v,u);
            low[u] = min(low[u],low[v]);
        }
        else if (v != p) low[u] = min(low[u],disc[v]);
    }
    fin[u] = num;
    return size[u];
}
pii x[3];
vi ans;
int need,no;
int doDFS2(int u) {
    if (need == 0) return 0;
    int i;
    ans[u] = x[0].second,need--;
    for (i = 0; i < adjList2[u].size(); i++) doDFS2(adjList2[u][i]);
    return 0;
}
int doDFS3(int u) {
    if (need == 0) return 0;
    int i;
    ans[u] = x[1].second,need--;
    for (i = 0; i < adjList[u].size(); i++) {
        if (ans[adjList[u][i]] == x[2].second) doDFS3(adjList[u][i]);
    }
    return 0;
}
int doDFS4(int u) {
    if (need == 0) return 0;
    int i;
    if ((disc[u] >= disc[no]) && (disc[u] < fin[no])) return 0;
    ans[u] = x[0].second,need--;
    for (i = 0; i < adjList[u].size(); i++) {
        int v = adjList[u][i];
        if (ans[v] == x[2].second) doDFS4(v);
    }
    return 0;
}
vector<int> find_split(int n,int a,int b,int c,vector<int> p,vector<int> q) {
    int i;
    x[0] = mp(a,1),x[1] = mp(b,2),x[2] = mp(c,3),sort(x,x+3);
    for (i = 0; i < p.size(); i++) {
        adjList[p[i]].pb(q[i]);
        adjList[q[i]].pb(p[i]);
    }
    for (i = 0; i < n; i++) disc[i] = low[i] = -1;
    doDFS(0,-1);
    int u = 0;
    while (1) {
        int h = -1;
        for (i = 0; i < adjList2[u].size(); i++) {
            int v = adjList2[u][i];
            if ((h == -1) || (size[v] > size[h])) h = v;
        }
        if (size[h] >= x[0].first) u = h;
        else break;
    }
    ans.resize(n,x[2].second);
    if (n-size[u] >= x[1].first) {
        need = x[0].first,doDFS2(u);
        need = x[1].first,doDFS3(parent[u]);
    }
    else {
        no = u,need = x[0].first,doDFS4(0);
        for (i = 0; i < adjList2[u].size(); i++) {
            int v = adjList2[u][i];
            if (low[v] < disc[u]) doDFS2(v);
        }
        if (need > 0) fill(ans.begin(),ans.end(),0);
        else need = x[1].first,doDFS3(u);
    }
    return ans;
}

Compilation message

split.cpp: In function 'int doDFS(int, int)':
split.cpp:63:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'int doDFS2(int)':
split.cpp:81:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList2[u].size(); i++) doDFS2(adjList2[u][i]);
                 ~~^~~~~~~~~~~~~~~~~~~~
split.cpp: In function 'int doDFS3(int)':
split.cpp:88:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'int doDFS4(int)':
split.cpp:98:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < adjList[u].size(); i++) {
                 ~~^~~~~~~~~~~~~~~~~~~
split.cpp: In function 'std::vector<int> find_split(int, int, int, int, std::vector<int>, std::vector<int>)':
split.cpp:107:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i = 0; i < p.size(); i++) {
                 ~~^~~~~~~~~~
split.cpp:116:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList2[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~~
split.cpp:130:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (i = 0; i < adjList2[u].size(); i++) {
                     ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 8 ms 5248 KB ok, correct split
3 Correct 7 ms 4992 KB ok, correct split
4 Correct 7 ms 4992 KB ok, correct split
5 Correct 8 ms 4992 KB ok, correct split
6 Correct 8 ms 4992 KB ok, correct split
7 Correct 134 ms 25700 KB ok, correct split
8 Runtime error 125 ms 43640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 7 ms 4992 KB ok, correct split
3 Correct 8 ms 5120 KB ok, correct split
4 Runtime error 168 ms 40416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 99 ms 15480 KB ok, correct split
3 Correct 37 ms 9216 KB ok, correct split
4 Correct 8 ms 5120 KB ok, correct split
5 Correct 121 ms 19832 KB ok, correct split
6 Correct 123 ms 19576 KB ok, correct split
7 Correct 120 ms 19320 KB ok, correct split
8 Correct 113 ms 20984 KB ok, correct split
9 Correct 119 ms 19192 KB ok, correct split
10 Correct 30 ms 8448 KB ok, no valid answer
11 Correct 45 ms 10240 KB ok, no valid answer
12 Correct 75 ms 14708 KB ok, no valid answer
13 Correct 97 ms 15352 KB ok, no valid answer
14 Correct 62 ms 14576 KB ok, no valid answer

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5120 KB ok, correct split
2 Correct 7 ms 5120 KB ok, no valid answer
3 Correct 8 ms 5120 KB ok, correct split
4 Correct 7 ms 4992 KB ok, correct split
5 Correct 7 ms 5120 KB ok, correct split
6 Correct 7 ms 4992 KB ok, correct split
7 Correct 7 ms 4992 KB ok, correct split
8 Correct 7 ms 4992 KB ok, correct split
9 Correct 9 ms 5376 KB ok, correct split
10 Correct 9 ms 5376 KB ok, correct split
11 Correct 8 ms 4992 KB ok, correct split
12 Correct 9 ms 5376 KB ok, correct split
13 Correct 7 ms 4992 KB ok, correct split
14 Correct 7 ms 5120 KB ok, correct split
15 Correct 7 ms 4992 KB ok, correct split
16 Correct 7 ms 4992 KB ok, correct split
17 Correct 7 ms 4992 KB ok, correct split
18 Correct 7 ms 4992 KB ok, correct split
19 Correct 8 ms 5120 KB ok, correct split
20 Correct 8 ms 5120 KB ok, correct split
21 Correct 9 ms 5376 KB ok, correct split
22 Correct 12 ms 5376 KB ok, correct split
23 Correct 9 ms 5504 KB ok, correct split
24 Correct 9 ms 5376 KB ok, correct split
25 Correct 9 ms 5376 KB ok, correct split
26 Correct 9 ms 5376 KB ok, correct split
27 Correct 9 ms 5376 KB ok, correct split
28 Correct 9 ms 5376 KB ok, correct split
29 Correct 8 ms 5120 KB ok, correct split
30 Correct 9 ms 5376 KB ok, correct split
31 Correct 9 ms 5248 KB ok, correct split
32 Correct 7 ms 5120 KB ok, correct split
33 Correct 8 ms 5120 KB ok, correct split
34 Correct 9 ms 5376 KB ok, correct split
35 Correct 9 ms 5376 KB ok, correct split
36 Correct 9 ms 5248 KB ok, correct split
37 Correct 10 ms 5376 KB ok, correct split
38 Correct 10 ms 5536 KB ok, correct split
39 Correct 10 ms 5376 KB ok, correct split
40 Correct 10 ms 5376 KB ok, correct split
41 Correct 8 ms 5248 KB ok, correct split
42 Correct 9 ms 5248 KB ok, correct split
43 Correct 10 ms 5376 KB ok, correct split
44 Correct 12 ms 5376 KB ok, correct split
45 Correct 9 ms 5376 KB ok, correct split
46 Correct 9 ms 5376 KB ok, correct split
47 Correct 9 ms 5376 KB ok, no valid answer
48 Correct 9 ms 5376 KB ok, correct split
49 Correct 9 ms 5504 KB ok, correct split
50 Correct 8 ms 4992 KB ok, no valid answer
51 Correct 7 ms 4992 KB ok, no valid answer
52 Correct 9 ms 5248 KB ok, no valid answer
53 Correct 10 ms 5376 KB ok, no valid answer
54 Correct 9 ms 5248 KB ok, no valid answer
55 Correct 9 ms 5376 KB ok, no valid answer
56 Correct 10 ms 5376 KB ok, no valid answer

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB ok, correct split
2 Correct 8 ms 5248 KB ok, correct split
3 Correct 7 ms 4992 KB ok, correct split
4 Correct 7 ms 4992 KB ok, correct split
5 Correct 8 ms 4992 KB ok, correct split
6 Correct 8 ms 4992 KB ok, correct split
7 Correct 134 ms 25700 KB ok, correct split
8 Runtime error 125 ms 43640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -