Submission #790436

#	Time	Username	Problem	Language	Result	Execution time	Memory
790436		Username4132	Vinjete (COI22_vinjete)	C++14	100 / 100	245 ms	93804 KiB

Main

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define forn(i, n) for(int i=0; i<(int)n; ++i)
#define forsn(i, s, n) for(int i=s; i<(int)n; ++i)
#define PB push_back
#define F first
#define S second

struct Vertex{
    int fsum, tsum;
    Vertex *l, *r;
    Vertex(int _fsum, int _tsum) : fsum(_fsum), tsum(_tsum), l(NULL), r(NULL) {}
    Vertex(Vertex* _l, Vertex* _r) : fsum(_l->fsum + _r->fsum), tsum(_l->tsum + _r->tsum), l(_l), r(_r) {}
};

const int MAXN = 100010;
int n, m, dummy, arr[2*MAXN];
Vertex* roots[MAXN];
vector<int> els;
vector<pair<int, pair<int, int>>> g[MAXN];

Vertex* build(int tl, int tr){
    if(tl == tr) return new Vertex(arr[tl], 0);
    int tm = (tl + tr)/2;
    return new Vertex(build(tl, tm), build(tm+1, tr));
}

Vertex* update(Vertex* v, int l, int r, int tl, int tr){
    if(v==NULL || l>r) return v;
    if(l==tl && r==tr) return new Vertex(v->fsum, v->fsum);
    int tm = (tl + tr)/2;
    if(v->l == NULL && v->r == NULL) return v;
    return new Vertex(update(v->l, l, min(r, tm), tl, tm), update(v->r, max(l, tm+1), r, tm+1, tr));
}

void dfs(int v, int p){
    for(auto to:g[v]) if(to.F!=p){
        int l = lower_bound(els.begin(), els.end(), to.S.F) - els.begin();
        int r = lower_bound(els.begin(), els.end(), to.S.S) - els.begin() - 1;
        roots[to.F] = update(roots[v], l, r, 0, m-2);
        dfs(to.F, v);
    }
}

int main(){
    scanf("%d %d", &n, &dummy);
    forn(i, n-1){
        int a, b, l, r; scanf("%d %d %d %d", &a, &b, &l, &r); --a, --b, --l;
        g[a].PB({b, {l, r}});
        g[b].PB({a, {l, r}});
        els.PB(l), els.PB(r);
    }
    sort(els.begin(), els.end());
    els.erase(unique(els.begin(), els.end()), els.end());
    m = els.size();
    forn(i, m-1) arr[i]=els[i+1]-els[i];
    roots[0] = build(0, m-2);
    dfs(0, 0);
    forsn(i, 1, n) printf("%d\n", roots[i]->tsum);
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     scanf("%d %d", &n, &dummy);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~
Main.cpp:50:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         int a, b, l, r; scanf("%d %d %d %d", &a, &b, &l, &r); --a, --b, --l;
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 16 / 16
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31