Submission #336146

#	Time	Username	Problem	Language	Result	Execution time	Memory
336146		gmyu	Railway (BOI17_railway)	C++14	100 / 100	254 ms	44140 KiB

railway

/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define sz(x) (int)(x).size()
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;

int N, M, K;
vi adjlist[MAXV];
map<int, int> pathmap[MAXV];
int dp[MAXV];

/// Euler ID for the tree
int p[MAXV], level[MAXV];
pii eulerRange[MAXV];
int eulerID = 0;

void buildEulerTree(int u, int lv) {

    eulerID++;
    eulerRange[u].first = eulerID;

    for(int i=0; i<adjlist[u].size(); i++) {
        int v = adjlist[u][i];
        if(v != p[u]) {
            p[v] = u;
            level[v] = lv + 1;
            buildEulerTree(v, lv+1);
        }
    }

    eulerRange[u].second = eulerID;
}
void initEuler() {
    /// root = 1
    adjlist[1].push_back(0);
    p[1] = 0; level[1] = 1;    //p[0] = 0; level[0] = 0;

    eulerID = 0;
    buildEulerTree(1, 1);
}
bool cmdFunc(const int& v1, const int& v2) {
    return eulerRange[v1].fst < eulerRange[v2].first;
}

/// tree info for calculate LCA
#define MAXLCALOG 20
int depth[MAXV], anc[MAXV][MAXLCALOG];

void prepLCA() {
    for(int i = 1; i <= N; i++) { anc[i][0] = p[i]; depth[i] = level[i] - 1;}

    for(int j = 1; j < MAXLCALOG; j++)
        for(int i = 1; i <= N; i++)
            anc[i][j] = anc[anc[i][j-1]][j-1];
}
int upD(int curr, int dist) {       /// go up by dist
    if(dist == 0) return curr;
    for(int k = MAXLCALOG - 1; k>=0; k--) {
        while(dist >= (1<<k) ) {
            curr = anc[curr][k];
            dist  -= (1<<k);
        }
        if(dist == 0) return curr;
    }
    return curr;
}
int getP(int curr, int wantedDepth) {   /// reach wanted depth
    for(int k = MAXLCALOG - 1; depth[curr] != wantedDepth; k--) {
        while(depth[curr] - (1<<k) >= wantedDepth) {
            curr = anc[curr][k];
        }
    }
    return curr;
}
int getLCA(int a, int b) {
    if(depth[a] > depth[b]) {
        return getLCA(b, a);
    }
    if(depth[a] < depth[b]) {
        b = getP(b, depth[a]);
    }
    for(int k = MAXLCALOG - 1; k > 0; k--) {
        while(anc[a][k] != anc[b][k]) {
            a = anc[a][k];
            b = anc[b][k];
        }
    }
    while(a != b) {
        a = p[a];
        b = p[b];
    }
    return a;
}

vi ans;
int dfsDP(int v, int pv) {
    if(sz(adjlist[v])==1 && v != 1) { // leaf
        if(dp[v] >= 2*K) ans.pb(pathmap[v][pv]);
        return dp[v];
    }
    for(int x : adjlist[v]) {
        if(x == pv) continue;
        dp[v] += dfsDP(x, v);
    }
    if(dp[v] >= 2*K && v != 1) ans.pb(pathmap[v][pv]);
    return dp[v];
}

int main() {
    debug = true; submit = false;
    if(submit) setIO("testName");

    int i, j, k;

    cin >> N >> M >> K;
    for(i=1; i<=N-1; i++) {
        int a, b; cin >> a >> b;
        adjlist[a].pb(b); adjlist[b].pb(a);
        pathmap[a][b] = i; pathmap[b][a] = i;
    }
    initEuler();
    prepLCA();

    vi cmd;
    for(i=1; i<=M; i++) {
        cmd.clear();
        int a; cin >> a;
        for(j=0; j<a; j++) { int b; cin >> b; cmd.pb(b); }
        sort(cmd.begin(), cmd.end(), cmdFunc);
        int b = cmd[0]; cmd.pb(b);
        for(j=0; j < sz(cmd) - 1; j++) {
            a = cmd[j]; b = cmd[j+1];
            int c = getLCA(a, b);
            dp[a]++; dp[c]--;
            dp[b]++; dp[c]--;
        }
    }

    dfsDP(1, 0);
    sort(ans.begin(), ans.end());
    cout << sz(ans) << endl;
    for(int x : ans) cout << x << " ";
    cout << endl;

}

Compilation message (stderr)

railway.cpp: In function 'void buildEulerTree(int, int)':
railway.cpp:74:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for(int i=0; i<adjlist[u].size(); i++) {
      |                  ~^~~~~~~~~~~~~~~~~~
railway.cpp: In function 'int main()':
railway.cpp:165:15: warning: unused variable 'k' [-Wunused-variable]
  165 |     int i, j, k;
      |               ^
railway.cpp: In function 'void setIO(std::string)':
railway.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
railway.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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