oj.uz

Submission #957844

# Submission time Handle Problem Language Result Execution time Memory
957844 2024-04-04T11:50:04 Z n3rm1n Railway (BOI17_railway) C++17
36 / 100
 73 ms 31692 KB 
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int MAXN = 2e5 + 1, MAXM = 6e4+10, MAXLOG = 22;
void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
int n, m, k;
vector < pair < int, int > > g[MAXN];
void read_graph()
{
    cin >> n >> m >> k;
    int from, to;
    for (int i = 1; i < n; ++ i)
    {
        cin >> from >> to;
        g[from].push_back({to, i});
        g[to].push_back({from, i});
    }
}

int p[MAXN], lvl[MAXN], tin[MAXN], tout[MAXN];
int tt = 0;
void dfs(int beg, int par, int depth)
{
    tt ++;
    p[beg] = par;
    lvl[beg] = depth;
    tin[beg] = tt;
    int nb;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        if(lvl[nb] == 0)
        {
            dfs(nb, beg, depth+1);

        }
    }
    tt ++;
    tout[beg] = tt;
}
int jump[MAXN][MAXLOG];
void fill_jump()
{
    for (int i = 1; i <= n; ++ i)
        jump[i][0] = p[i];
    for (int j = 1; j < MAXLOG; ++ j)
        for (int i = 1; i <= n; ++ i)
            jump[i][j] = jump[jump[i][j-1]][j-1];
}
int move_up(int v, int dist)
{
    for (int i = 0; (1 << i) <= dist; ++ i)
    {
        if((1 << i) & dist)
            v = jump[v][i];
    }
    return v;
}
int lca(int u, int v)
{
    if(lvl[u] > lvl[v])swap(u, v);
    int diff = lvl[v] - lvl[u];
    v = move_up(v, diff);
    if(u == v)return u;
    for (int i = MAXLOG - 1; i >= 0; -- i)
    {
        if(jump[u][i] != jump[v][i])
        {
            u = jump[u][i];
            v = jump[v][i];
        }
    }
    return p[u];
}
int s;
bool cmp(int x, int y)
{
    return (tout[x] < tout[y]);
}
int cnt[MAXN];
int ans[MAXN];
int dfs2(int beg, int par)
{
    int take_up = cnt[beg];
    int nb, id;
    int from_down;
    for (int i = 0; i < g[beg].size(); ++ i)
    {
        nb = g[beg][i].first;
        id = g[beg][i].second;

        if(nb != par)
        {
            from_down = dfs2(nb, beg);
            take_up += from_down;
            ans[id] += from_down;
        }
    }

    return take_up;
}
void read_queries()
{
    int xx, lcaa;
    vector < int > que;
    for (int i = 1; i <= m; ++ i)
    {
        cin >> s >> xx;
        que.clear();
        que.push_back(xx);
        for (int j = 2; j <= s; ++ j)
        {
            cin >> xx;
            que.push_back(xx);

        }
        sort(que.begin(), que.end(), cmp);
        lcaa = que[0];
        for (int j = 1; j < que.size(); ++ j)
        {
            xx = que[j];
            cnt[lcaa] ++;
            cnt[xx] ++;
            lcaa = lca(lcaa, xx);
            cnt[lcaa] -= 2;
        }
    }

}
int main()
{
    speed();

    read_graph();
    dfs(1, 0, 1);
    fill_jump();
    read_queries();
    dfs2(1, 0);


    vector < int > anss;
    for (int i = 1; i <= n; ++ i)
    {
        if(ans[i] >= k)anss.push_back(i);
    }

    cout << anss.size() << endl;
    for (int i = 0; i < anss.size(); ++ i)
        cout << anss[i] << " ";
    cout << endl;
    return 0;
}

Compilation message

railway.cpp: In function 'void dfs(int, int, int)':
railway.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'int dfs2(int, int)':
railway.cpp:92:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for (int i = 0; i < g[beg].size(); ++ i)
      |                     ~~^~~~~~~~~~~~~~~
railway.cpp: In function 'void read_queries()':
railway.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for (int j = 1; j < que.size(); ++ j)
      |                         ~~^~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:153:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  153 |     for (int i = 0; i < anss.size(); ++ i)
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 7 ms 11100 KB Output is correct
3 Incorrect 7 ms 11100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 7 ms 11100 KB Output is correct
3 Incorrect 7 ms 11100 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 30872 KB Output is correct
2 Correct 2 ms 8284 KB Output is correct
3 Correct 57 ms 30644 KB Output is correct
4 Correct 65 ms 29988 KB Output is correct
5 Correct 57 ms 30664 KB Output is correct
6 Correct 72 ms 31180 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 26704 KB Output is correct
2 Correct 51 ms 23048 KB Output is correct
3 Correct 57 ms 22652 KB Output is correct
4 Correct 64 ms 22620 KB Output is correct
5 Correct 54 ms 22620 KB Output is correct
6 Correct 49 ms 26704 KB Output is correct
7 Correct 46 ms 26712 KB Output is correct

Subtask #5
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 26704 KB Output is correct
2 Correct 51 ms 23048 KB Output is correct
3 Correct 57 ms 22652 KB Output is correct
4 Correct 64 ms 22620 KB Output is correct
5 Correct 54 ms 22620 KB Output is correct
6 Correct 49 ms 26704 KB Output is correct
7 Correct 46 ms 26712 KB Output is correct
8 Correct 55 ms 26452 KB Output is correct
9 Correct 73 ms 27276 KB Output is correct
10 Correct 59 ms 31692 KB Output is correct
11 Correct 55 ms 31512 KB Output is correct
12 Correct 37 ms 23124 KB Output is correct
13 Correct 49 ms 23000 KB Output is correct
14 Incorrect 51 ms 23292 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8280 KB Output is correct
2 Correct 7 ms 11100 KB Output is correct
3 Incorrect 7 ms 11100 KB Output isn't correct
4 Halted 0 ms 0 KB -