oj.uz

Submission #1004229

# Submission time Handle Problem Language Result Execution time Memory
1004229 2024-06-21T06:38:21 Z vjudge1 Kitchen (BOI19_kitchen) C++17
0 / 100
 1000 ms 2652 KB 
/* :) */
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pll pair<ll, ll>
const int sz = 1e5+5;
vector<ll>g[sz];
ll used[sz], par[sz];
map<pll, ll>mp, ans;
 
void dfs(ll v)
{
    used[v] = 1;
    for (auto u : g[v]){
        if (used[u] == 0){
            par[u] = v;
            dfs(u);
        }
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n, m, k;
    cin>>n>>m>>k;
    for (ll i = 1; i<=n-1; i++){
        ll u, v;
        cin>>u>>v;
        ans[{u, v}] = ans[{v, u}] = i;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    while (m--){
        ll f, x, y;
        cin>>f>>x;
        set<pll>s;
        for (ll i = 2; i<=f; i++){
            cin>>y;
            dfs(x);
            while (par[y] != x){
                if (y > par[y]) s.insert({par[y], y});
                else            s.insert({y, par[y]});
                y = par[y];
            }
            if (y > par[y]) s.insert({par[y], y});
            else            s.insert({y, par[y]});
            x = y;
            for (ll j = 1; j<=n; j++){
                par[j] = used[j] = 0;
            }
        }
        for (auto i : s){
            mp[{i.first, i.second}]++;
        }
    }
    vector<ll>v;
    for (auto i : mp){
        if (i.second >= k){
            v.push_back(ans[{i.first.first, i.first.second}]);
        }
        //cout<<i.first.first<<' '<<i.first.second<<endl;
    }
    cout<<v.size()<<endl;
    for (ll i = 0; i<v.size(); i++){
        cout<<v[i]<<' ';
    }
}

Compilation message

kitchen.cpp: In function 'int main()':
kitchen.cpp:66:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |     for (ll i = 0; i<v.size(); i++){
      |                    ~^~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 2652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 2652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 2652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1090 ms 2648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 28.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 2652 KB Time limit exceeded
2 Halted 0 ms 0 KB -