oj.uz

Submission #745498

# Submission time Handle Problem Language Result Execution time Memory
745498 2023-05-20T08:43:39 Z MohamedAliSaidane Split the Attractions (IOI19_split) C++14
22 / 100
 483 ms 1048576 KB 
#include <bits/stdc++.h>
#include "split.h"
using namespace std;


typedef long long ll;

typedef vector<int> vi;

#define pb push_back
#define ff first
#define ss second

const int nax = 1e5 + 4;
int n, m, a, b, c;
vi adj[nax];
vi ans;
int d[nax], sz[nax];
bool ok = false;
int head1, id1;
int head2, id2;
int id3;
int card[4];
void dfs(int x, int p = 0)
{
    sz[x] = 1;
    d[x] = d[p] + 1;
    for(auto e: adj[x])
    {
        if(e != p)
        {
            dfs(e, x);
            sz[x] += sz[e];
        }
    }
    if(ok)
        return;
    if(sz[x] >= a && n - sz[x] >= b)
    {
        ok = true;
        head1 = x, id1 = 1;
        head2 = p, id2 = 2;
        id3 = 3;
    }
    else if(sz[x] >= b && n - sz[x] >= a)
    {
        ok = true;
        head1 = x, id1 = 2;
        head2 = p, id2 = 1;
        id3 = 3;
    }
    else if(sz[x] >= a && n - sz[x] >= c)
    {
        ok = true;
        head1 = x, id1 = 1;
        head2 = p, id2 = 3;
        id3 = 2;
    }
    else if(sz[x] >= c && n - sz[x] >= a)
    {
        ok = true;
        head1 = x, id1 = 3;
        head2 = p, id2 = 1;
        id3 = 2;
    }
    else if(sz[x] >= b && n - sz[x] >= c)
    {
        ok = true;
        head1 = x, id1 = 2;
        head2 = p, id2 = 3;
        id3 = 1;
    }
    else if(sz[x] >= c && n -  sz[x] >= b)
    {
        ok = true;
        head1 = x, id1 = 3;
        head2 = p, id2 = 3;
        id3 = 1;
    }
}
int curid = 0;
int cnt = 0;
void dfs2(int x, int p)
{
    ans[x] = curid;
    cnt++;
    for(auto e: adj[x])
    {
        if(cnt == card[curid])
            return;
        if(e != p)
        {
            dfs2(e, x);
        }
    }
}
vi find_split(int N, int A, int B, int C, vi P, vi Q)
{
    n = N, a = A, b = B, c = C;
    m = P.size();
    for(int i =0 ; i < n; i++)
        adj[i].clear();
    card[1] = a, card[2] =  b, card[3] = c;
    for(int i = 0; i < m; i ++)
    {
        adj[P[i]].pb(Q[i]);
        adj[Q[i]].pb(P[i]);
    }
    ans.assign(n, 0);
    d[0] = -1;
    dfs(0, 0);
    if(!ok)
        return ans;
    curid = id1;
    dfs2(head1, head2);
    curid = id2;
    cnt = 0;
    dfs2(head2, head1);
    for(int i = 0 ; i < n ; i++)
    {
        if(ans[i] == 0)
            ans[i] = id3;
    }
    return ans;
}
/*
int32_t main()
{
    int N, M, A, B, C;
    cin >> N >> M >> A >> B >> C;
    vi P(M), Q(M);
    for(int i = 0; i < M; i++)
        cin >> P[i] >> Q[i];
    vi ANS = find_split(N, A, B, C, P, Q);
    for(auto e: ANS)
        cout << e << ' ';
}
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB ok, correct split
2 Runtime error 482 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2660 KB ok, correct split
2 Runtime error 480 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB ok, correct split
2 Correct 54 ms 10072 KB ok, correct split
3 Correct 20 ms 5660 KB ok, correct split
4 Correct 2 ms 2660 KB ok, correct split
5 Correct 79 ms 12648 KB ok, correct split
6 Correct 61 ms 12384 KB ok, correct split
7 Correct 61 ms 12132 KB ok, correct split
8 Correct 76 ms 13656 KB ok, correct split
9 Correct 70 ms 12008 KB ok, correct split
10 Correct 17 ms 5204 KB ok, no valid answer
11 Correct 24 ms 6348 KB ok, no valid answer
12 Correct 45 ms 10296 KB ok, no valid answer
13 Correct 56 ms 10140 KB ok, no valid answer
14 Correct 45 ms 10448 KB ok, no valid answer

Subtask #4
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 483 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB ok, correct split
2 Runtime error 482 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -