kattis

Solution to Kattis problems

https://github.com/jerryxu20/kattis

Science Score: 44.0%

This score indicates how likely this project is to be science-related based on various indicators:

  • CITATION.cff file
    Found CITATION.cff file
  • codemeta.json file
    Found codemeta.json file
  • .zenodo.json file
    Found .zenodo.json file
  • DOI references
  • Academic links in README
  • Academic email domains
  • Institutional organization owner
  • JOSS paper metadata
  • Scientific vocabulary similarity
    Low similarity (0.2%) to scientific vocabulary
Last synced: 10 months ago · JSON representation ·

Repository

Solution to Kattis problems

Basic Info
  • Host: GitHub
  • Owner: jerryxu20
  • Language: C++
  • Default Branch: main
  • Size: 809 KB
Statistics
  • Stars: 0
  • Watchers: 1
  • Forks: 0
  • Open Issues: 0
  • Releases: 0
Created over 3 years ago · Last pushed about 1 year ago
Metadata Files
Citation

Owner

  • Name: Jerry Xu
  • Login: jerryxu20
  • Kind: user

2nd year software engineering

Citation (citations.cpp)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vld;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
typedef vector<bool> vb;
typedef tuple<int,int,int> ti;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vi> vii;
typedef vector<vii> viii;

template<class T> using PQ = priority_queue<T>;
template<class T> using PQG = priority_queue<T, vector<T>, greater<T>>;

#define rep(i, a, b) for (int i=a; i<(b); i++)
#define FOR(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(x,A) for (auto& x : A)

#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define ins insert

const int MOD = 1000000007;
const char nl = '\n';
const int MAXN = 1e5;
vi adj[MAXN];
// # of nodes, total time, answer for subtree
ll cnt[MAXN], sub[MAXN], ans[MAXN]; 

void dfs(int node) {
    // read citations
    sub[node] += 1;

    // answer starts with time to read itself
    ans[node] = sub[node];
    cnt[node] = 1;


    /*
        ans = (time to read itself) + (1 * sz(subtree)) + ans(children)

        We need to read ourself. We incur 1 cost for every node in the subtree (including node itself) 
        because we need to read citations first. 

        We include the borrowing time of all children by themselves. Then we have to extend the
        borrowing time of all children. 

        Whatever child we read first, all the nodes in the subtrees of other unread children and our node itself 
        incur the time to read that child. Imagine all our children are leafs. Then the best order to 
        read them is shortest first. This is because the cost is either a + (a + b) or b + (a + b). 

        Now if the children are not leafs, but there are only two of them with (cnt_a, t_a) and (cnt_b, t_b),
        then we either incur cnt_a * t_b or cnt_b * t_a and there is a greedy choice that is best. 
        We can almost think of each node in the child's subtree as a seperate leaf node with cost t/cnt.      
    */

    trav(nxt, adj[node]) {
        // do shortest first
        dfs(nxt);
        cnt[node] += cnt[nxt];
        sub[node] += sub[nxt];

        ans[node] += ans[nxt];
        ans[node] += cnt[nxt];
    }

    sort(all(adj[node]), [&] (auto &a, auto &b) {
        return sub[a] * cnt[b] < sub[b] * cnt[a];          
    });

    int nodes = cnt[node];
    trav(nxt, adj[node]) {
        nodes -= cnt[nxt];
        ans[node] += sub[nxt] * nodes; 
    }

    return;
}


int solve(int tt) {
    int n; cin >> n;

    rep(i, 0, n) {
        cin >> sub[i];
        int m; cin >> m;
        while(m--) {
            int x; cin >> x;
            x--;
            adj[i].pb(x);
        }
    }
    
    dfs(0);
    cout << ans[0] << endl;
    tt++;
    return 0;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        if (solve(i)) break;
    }
    T++;
    return 0;
}

GitHub Events

Total
  • Push event: 11
Last Year
  • Push event: 11