Submission #1195359

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195359		FIFI_cpp	Vinjete (COI22_vinjete)	C++20	56 / 100	179 ms	22844 KiB

Main

#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>

#define all(a) a.begin(), a.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define pb push_back
#define ppi pair<int,pair<int,int>>
#define int int64_t

using namespace std;
//    /\_/\
//   (= ._.)
//   / >  \>
// encouraging cat
const int INF = 10000000000000000;
//const int mod = 1000000007;
const int mod = 998244353;
const int MAXN = 200005;
//ifstream fin('xor.in');
//ofstream fout('xor.out');
struct Data {
    int mi, freq;
};
int lazy[MAXN * 4];
Data t[MAXN * 4];
Data merge(Data a, Data b)
{
    if (a.mi == b.mi)
    {
        return {a.mi, a.freq + b.freq};
    }
    else if (a.mi < b.mi)
    {
        return a;
    }
    else
    {
        return b;
    }
}
void build(int v, int tl, int tr)
{
    if (tl == tr)
    {
        t[v].mi = 0;
        t[v].freq = 1;
    }
    else
    {
        int tm = (tl + tr) / 2;
        build(v*2, tl, tm);
        build(v*2+1, tm+1, tr);
        t[v] = merge(t[v*2], t[v*2 + 1]);
    }
}
void push(int v)
{
    lazy[v * 2] += lazy[v];
    lazy[v * 2 + 1] += lazy[v];
    t[v * 2].mi += lazy[v];
    t[v * 2 + 1].mi += lazy[v];
    lazy[v] = 0;
}
void update(int v,int tl,int tr,int l,int r, int value)
{
    if (l > r) 
        return;
    if (l == tl && tr == r)
    {
        t[v].mi += value;
        lazy[v] += value;
    }
    else
    {
        push(v);
        int tm = (tl + tr) / 2;
        update(v*2, tl, tm, l, min(r, tm), value);
        update(v*2+1, tm+1, tr, max(l, tm+1), r, value);
        t[v] = merge(t[v * 2], t[v * 2 + 1]);
    }
}
Data query(int v, int tl, int tr, int l, int r) {
    if (l > r)
        return {INF, 1};
    if (l == tl && tr == r)
        return t[v];
    push(v);
    int tm = (tl + tr) / 2;
    return merge(query(v*2, tl, tm, l, min(r, tm)), query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
struct Edge {
    int dest, l, r;
};
int n,m;
vector<vector<Edge>> adj;
int res[MAXN];
void dfs(int node, int p)
{
    Data q = query(1, 1, m, 1, m);
    if (q.mi > 0)
    {
        res[node] = m;
    }
    else
    {
        res[node] = m - q.freq;
    }
    for (auto edge: adj[node])
    {
        if (edge.dest == p)
        {
            continue;
        }
        update(1, 1, m, edge.l, edge.r, 1);
        dfs(edge.dest, node);
        update(1, 1, m, edge.l, edge.r, -1);
    }
}
signed main()
{
    cin >> n >> m;
    build((int)1, (int)1, m);
    adj.resize(n);
    for (int i = 0;i < n - 1;i++)
    {
        int u,v,l,r;
        cin >> u >> v >> l >> r;
        u--,v--;
        adj[u].pb({v,l,r});
        adj[v].pb({u,l,r});
    }
    dfs(0, -1);
    for (int i = 1;i < n;i++)
    {
        cout << res[i] << '\n';
    }
    return 0;
}

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