제출 #1004429

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1004429		hacizadal	Railway (BOI17_railway)	C++17	23 / 100	1084 ms	54136 KiB

railway

/* :) */
#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 in[sz], out[sz], par[sz], parent[sz][20], t;
map<pll, ll>mp, ans;

void dfs(ll v, ll p)
{
    parent[v][0] = p;
    for (ll i = 1; i<20; i++){
        parent[v][i] = parent[parent[v][i-1]][i-1];
    }
    in[v] = ++t;
    for (auto u : g[v]){
        if (u != p){
            par[u] = v;
            dfs(u, v);
        }
    }
    out[v] = ++t;
}

ll lca(ll x, ll y)
{
    if (in[x] <= in[y] and out[y] <= out[x]) return x;
    for (ll i = 19; i>=0; i--){
        int p = parent[x][i];
        if (!(in[p] <= in[y] and out[y] <= out[p])){
            x = p;
        }
    }
    return parent[x][0];
}

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);
    }
    in[0] = 0;
    dfs(1, 0);
    out[0] = ++t;
    while (m--){
        ll f, x, y;
        cin>>f>>x;
        set<pll>s;
        for (ll i = 2; i<=f; i++){
            cin>>y;
            ll Y = y;
            ll l = lca(x, y);
            while (x != l){
                if (par[x] > x) s.insert({x, par[x]});
                else            s.insert({par[x], x});
                x = par[x];
            }

            while (y != l){
                if (par[y] > y) s.insert({y, par[y]});
                else            s.insert({par[y], y});
                y = par[y];
            }

            x = Y;
        }
        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<<v.size()<<endl;
    for (ll i = 0; i<v.size(); i++){
        cout<<v[i]<<' ';
    }
}

컴파일 시 표준 에러 (stderr) 메시지

railway.cpp: In function 'int main()':
railway.cpp:88: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]
   88 |     for (ll i = 0; i<v.size(); i++){
      |                    ~^~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 7
• Subtask 4: 0 / 29
• Subtask 5: 0 / 16
• Subtask 6: 0 / 25