oj.uz

Submission #464962

# Submission time Handle Problem Language Result Execution time Memory
464962 2021-08-14T16:10:22 Z blue Meetings 2 (JOI21_meetings2) C++17
4 / 100
 4000 ms 6220 KB 
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;

const int maxN = 200'000;
const int logN = 19;

int N;
vector<int> edge[1+maxN];

int anc[1+maxN][1+logN];
vector<int> depth(1+maxN);

void dfs(int u)
{
    for(int v: edge[u])
    {
        if(anc[u][0] == v) continue;
        anc[v][0] = u;
        depth[v] = depth[u] + 1;
        dfs(v);
    }
}

int lca(int u, int v)
{
    if(depth[u] > depth[v]) swap(u, v);
    for(int e = logN; e >= 0; e--)
    {
        if(depth[ anc[v][e] ] >= depth[u])
            v = anc[v][e];
    }
    if(u == v) return u;

    for(int e = logN; e >= 0; e--)
    {
        if(anc[u][e] == anc[v][e]) continue;
        u = anc[u][e];
        v = anc[v][e];
    }

    u = anc[u][0];
    return u;
}

int dist(int u, int v)
{
    return depth[u] + depth[v] - 2*depth[lca(u, v)];
}






int main()
{
    cin >> N;
    for(int e = 1; e <= N-1; e++)
    {
        int A, B;
        cin >> A >> B;
        edge[A].push_back(B);
        edge[B].push_back(A);
    }

    anc[1][0] = anc[0][0] = 0;
    depth[1] = 1;
    dfs(1);




    for(int e = 1; e <= logN; e++)
    {
        for(int u = 0; u <= N; u++)
        {
            anc[u][e] = anc[ anc[u][e-1] ][e-1];
        }
    }




    vector<int> res(N+1, 0);
    for(int mask = 2; mask < (1 << (N+1)); mask += 2)
    {
        int J = 0;
        vector<bool> present(1+N, 0);
        for(int u = 1; u <= N; u++)
        {
            if(mask & (1 << u))
            {
                present[u] = 1;
                J++;
            }
        }

        vector<int> sm(1+N, 0);
        for(int u = 1; u <= N; u++)
        {
            if(mask & (1 << u))
            {
                for(int mp = 1; mp <= N; mp++)
                {
                    sm[mp] += dist(u, mp);
                }
            }
        }

        int xs = 0;
        int mindist = 1e9;
        for(int mp = 1; mp <= N; mp++)
        {
            if(sm[mp] < mindist)
            {
                xs = 1;
                mindist = sm[mp];
            }
            else if(sm[mp] == mindist)
            {
                xs++;
            }
        }

        res[J] = max(res[J], xs);
    }

    for(int u = 1; u <= N; u++) cout << res[u] << ' ';
    cout << '\n';
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 261 ms 5776 KB Output is correct
5 Correct 269 ms 5776 KB Output is correct
6 Correct 254 ms 5708 KB Output is correct
7 Correct 265 ms 5776 KB Output is correct
8 Correct 620 ms 5772 KB Output is correct
9 Correct 1359 ms 5772 KB Output is correct
10 Correct 1438 ms 5772 KB Output is correct
11 Correct 1463 ms 5772 KB Output is correct
12 Correct 1288 ms 5768 KB Output is correct
13 Correct 1459 ms 5768 KB Output is correct
14 Correct 277 ms 5776 KB Output is correct
15 Correct 232 ms 5776 KB Output is correct
16 Correct 647 ms 5772 KB Output is correct
17 Correct 1445 ms 5772 KB Output is correct
18 Correct 1440 ms 5780 KB Output is correct
19 Correct 617 ms 5828 KB Output is correct
20 Correct 1414 ms 5772 KB Output is correct
21 Correct 556 ms 5772 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 261 ms 5776 KB Output is correct
5 Correct 269 ms 5776 KB Output is correct
6 Correct 254 ms 5708 KB Output is correct
7 Correct 265 ms 5776 KB Output is correct
8 Correct 620 ms 5772 KB Output is correct
9 Correct 1359 ms 5772 KB Output is correct
10 Correct 1438 ms 5772 KB Output is correct
11 Correct 1463 ms 5772 KB Output is correct
12 Correct 1288 ms 5768 KB Output is correct
13 Correct 1459 ms 5768 KB Output is correct
14 Correct 277 ms 5776 KB Output is correct
15 Correct 232 ms 5776 KB Output is correct
16 Correct 647 ms 5772 KB Output is correct
17 Correct 1445 ms 5772 KB Output is correct
18 Correct 1440 ms 5780 KB Output is correct
19 Correct 617 ms 5828 KB Output is correct
20 Correct 1414 ms 5772 KB Output is correct
21 Correct 556 ms 5772 KB Output is correct
22 Execution timed out 4067 ms 6220 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5708 KB Output is correct
2 Correct 3 ms 5708 KB Output is correct
3 Correct 3 ms 5708 KB Output is correct
4 Correct 261 ms 5776 KB Output is correct
5 Correct 269 ms 5776 KB Output is correct
6 Correct 254 ms 5708 KB Output is correct
7 Correct 265 ms 5776 KB Output is correct
8 Correct 620 ms 5772 KB Output is correct
9 Correct 1359 ms 5772 KB Output is correct
10 Correct 1438 ms 5772 KB Output is correct
11 Correct 1463 ms 5772 KB Output is correct
12 Correct 1288 ms 5768 KB Output is correct
13 Correct 1459 ms 5768 KB Output is correct
14 Correct 277 ms 5776 KB Output is correct
15 Correct 232 ms 5776 KB Output is correct
16 Correct 647 ms 5772 KB Output is correct
17 Correct 1445 ms 5772 KB Output is correct
18 Correct 1440 ms 5780 KB Output is correct
19 Correct 617 ms 5828 KB Output is correct
20 Correct 1414 ms 5772 KB Output is correct
21 Correct 556 ms 5772 KB Output is correct
22 Execution timed out 4067 ms 6220 KB Time limit exceeded
23 Halted 0 ms 0 KB -