제출 #1337051

#제출 시각아이디문제언어결과실행 시간메모리
1337051hauserlRailway (BOI17_railway)C++20
36 / 100
103 ms42968 KiB
#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct T {
    ll v;
    ll tinV;

    bool operator<(const T& o) const {
        return tinV < o.tinV;
    }
};

ll n,m,k; 

vector<vector<pair<ll, ll>>> adj;
vector<ll> edgeToP;

vector<vector<T>> chosenC;
vector<ll> countS;

ll l;
ll timer;
vector<ll> tin, tout;
vector<vector<ll>> up;

vector<ll> pathPre;
vector<ll> pathPrefix;




void dfs(ll u, ll p) {
    tin[u] = timer++;
    up[u][0] = p;
    for (ll i = 1; i <= l; i++) {
        up[u][i] = up[up[u][i-1]][i-1];
    }

    for (const auto& v : adj[u]) {
        if (v.first != p) {
            edgeToP[v.first] = v.second;
            dfs(v.first, u);
        }
    }

    tout[u] = timer++;
}

bool isAncestor(ll u, ll v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

ll lca(ll u, ll v) {
    if (isAncestor(u,v)) return u;
    if (isAncestor(v,u)) return v;

    for (ll i = l; i >= 0; i--) {
        if (!isAncestor(up[u][i], v)) u = up[u][i];
    }
    return up[u][0];
}

void preprocess(ll root) {
    tin.resize(n+1);
    tout.resize(n+1);
    timer = 0;
    l = ceil(log2(n)); if (l == 0) l = 1;
    up.assign(n+1, vector<ll>(l+1));
    dfs(root, root);
}
  


ll dfsSubtree(ll u, ll p) {

    ll sum = pathPre[u];

    for (const auto& v : adj[u]) {
        if (v.first != p) sum += dfsSubtree(v.first, u);
    }

    pathPrefix[u] = sum;
    return sum;
}



int main() {

    scanf("%lld %lld %lld",&n,&m,&k);
    adj.resize(n+1, {});
    edgeToP.resize(n+1, -1);
    countS.resize(n, 0);
    chosenC.resize(m+1, {});

    for (ll i = 1; i < n; i++) {
        ll a,b; scanf("%lld %lld",&a,&b);
        adj[a].push_back({b, i});
        adj[b].push_back({a, i});
    }
    
    preprocess(1);

    for (ll i = 1; i <= m; i++) {
        ll s; scanf("%lld",&s);
        for (ll j = 0; j < s; j++) {
            ll z; scanf("%lld",&z);
            chosenC[i].push_back({z, tin[z]});
        }
    }

    pathPre.resize(n+1, 0);
    for (ll i = 1; i <= m; i++) {
        // dfs sortierung mit tin

        sort(chosenC[i].begin(), chosenC[i].end());

        for (ll j = 0; j < chosenC[i].size(); j++) {

            // make paths form u1 -> u2, u2->u3 , ..., un -> u1

            ll a = chosenC[i][j].v;
            ll b = chosenC[i][(j+1)%chosenC[i].size()].v;

            pathPre[a]++;
            pathPre[b]++;
            pathPre[lca(a,b)] -= 2;
        }
    }

    // subtree (only count if val/2 >= k)
    pathPrefix.resize(n+1, -1);
    dfsSubtree(1, -1);

    set<ll> addRails;
    for (ll i = 2; i <= n; i++) {
        if (pathPrefix[i] / 2 >= k) addRails.insert(i);
    }

    // printf("%zu \n", addRails.size());
    printf("%lld \n", (ll)addRails.size());


    for (const auto& a : addRails) printf("%lld ", edgeToP[a]);


    // (can you do that for every m and compute at subtrees at end and then half everything or do you have to do before?)
    // subtree sum and then half


    return 0;
}

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

railway.cpp: In function 'int main()':
railway.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%lld %lld %lld",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:98:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         ll a,b; scanf("%lld %lld",&a,&b);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~~
railway.cpp:106:20: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         ll s; scanf("%lld",&s);
      |               ~~~~~^~~~~~~~~~~
railway.cpp:108:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |             ll z; scanf("%lld",&z);
      |                   ~~~~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...