kattis

https://github.com/dgonzalezarbelo/kattis

Science Score: 31.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
○
DOI references
○
Academic links in README
○
Academic email domains
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Unable to calculate vocabulary similarity

Last synced: 10 months ago · JSON representation ·

Repository

Basic Info

Host: GitHub
Owner: dgonzalezarbelo
Language: C++
Default Branch: main
Size: 60.5 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

Login: dgonzalezarbelo
Kind: user

Repositories: 1
Profile: https://github.com/dgonzalezarbelo

Citation (citations.cpp)

#include <bits/stdc++.h>
#pragma warning (disable : 4996)
using namespace std;

#define rep(i, a, b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define mp make_pair

const double EPS = 1e-9;
const double INF = 1e9; //1e18 tambien suele ir bien
using ll = long long int;
using ull = unsigned long long;
using ii = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vii = vector<ii>;
using vvii = vector<vii>;
using vb = vector<bool>;
using vvb = vector<vb>;
using db = double;
using vdb = vector<db>;
using ldb = long double; //100 ceros pero poca precision decimal

vvi al;
vi costes, acumulados;

int dfs(int a) {
    int n_hijos = 0;
    for(int b : al[a]) 
        n_hijos += dfs(b);
    // Los ordenamos por lo que tarda cada rama. Lo optimo es priorizar las que menos tardan
    sort(all(al[a]), [&](int x, int y) {
            return acumulados[x] < acumulados[y];
        });
    int acum = 0, cur_acum = 0;
    for(int b : al[a]) {
        cur_acum += acumulados[b];
        acum += cur_acum;
    }
    acum += 1 + costes[a];
    acumulados[a] = acum;
    // El coste de esta rama es el de hacer las cosas de forma optima
    return n_hijos + 1;
}

int sol;

int dfs2(int a, int acum_prev) {
    int t = 1 + acum_prev;
    for(int b : al[a])
        t = dfs2(b, t);
    t += costes[a];
    sol += t;
    return t;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    sol = 0;
    int n; cin >> n;
    al.assign(n, {});
    costes.assign(n, {});
    acumulados.assign(n, {});
    rep(i,0,n) {
        int k; cin >> k;
        costes[i] = k;
        int f; cin >> f;
        while(f--) {
            int a; cin >> a;
            a--;
            al[i].push_back(a);
        }
    }
    dfs(0);
    dfs2(0,0);
    cout << sol << endl;
    return 0;
}

ecosyste.ms

Data

Tools

Indexes

Applications

Experiments

Open Source Science