제출 #1337044

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

struct T {
    int v;
    int tinV;

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

int n,m,k; 

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

vector<vector<T>> chosenC;
vector<int> countS;

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

vector<int> pathPre;
vector<int> pathPrefix;




void dfs(int u, int p) {
    tin[u] = timer++;
    up[u][0] = p;
    for (int 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(int u, int v) {
    return tin[u] <= tin[v] && tout[u] >= tout[v];
}

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

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

void preprocess(int 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<int>(l+1));
    dfs(root, root);
}
  


int dfsSubtree(int u, int p) {

    int 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("%d %d %d",&n,&m,&k);
    adj.resize(n+1, {});
    edgeToP.resize(n+1, -1);
    countS.resize(n, 0);
    chosenC.resize(m+1, {});

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

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

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

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

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

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

            int a = chosenC[i][j].v;
            int 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<int> addRails;
    for (int i = 1; i <= n; i++) {
        if (pathPrefix[i] / 2 >= k) addRails.insert(i);
    }

    printf("%d \n", addRails.size());

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



    return 0;
}

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

railway.cpp: In function 'int main()':
railway.cpp:141:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wformat=]
  141 |     printf("%d \n", addRails.size());
      |             ~^      ~~~~~~~~~~~~~~~
      |              |                   |
      |              int                 std::set<int>::size_type {aka long unsigned int}
      |             %ld
railway.cpp:91:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     scanf("%d %d %d",&n,&m,&k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
railway.cpp:98:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         int a,b; scanf("%d %d",&a,&b);
      |                  ~~~~~^~~~~~~~~~~~~~~
railway.cpp:106:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  106 |         int s; scanf("%d",&s);
      |                ~~~~~^~~~~~~~~
railway.cpp:108:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |             int z; scanf("%d",&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...