답안 #532663

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
532663	2022-03-03T15:02:21 Z	mat50013	Dynamic Diameter (CEOI19_diameter)	C++11	0 / 100	5000 ms	152320 KB

diameter

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
const int NMAX(100005);
vector<pair<int, ll> > G[NMAX];
vector<int> frati[NMAX];
map<pair<int, int>, vector<pair<int, int> > > mp;
bool dead[NMAX], mark[NMAX], viz[NMAX];
int pas, dim, sz[NMAX], tip[NMAX], cnt, baza, mov, id[NMAX];
ll dist[NMAX], maxx[NMAX];

struct SEGTREE
{
    vector<ll> Arb, lazy;
    vector<int> in, out;
    int cati;
    inline void init(int n)
    {
        cati = n;
        int put = 1;
        while(put <= n)
            put <<= 1;
        put <<= 1;
        Arb.resize(put), in.resize(put), out.resize(put), lazy.resize(put << 1);
    }
    inline void build(int nod, int st, int dr)
    {
        if(st == dr)
        {
            Arb[nod] = dist[st];
            return;
        }
        int mij = (st + dr) / 2;
        build(2 * nod, st, mij);
        build(2 * nod + 1, mij + 1, dr);
        Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
    }
    inline void push(int nod){
        if(lazy[nod]){
            Arb[nod] += lazy[nod];
            lazy[2 * nod] += lazy[nod];
            lazy[2 * nod + 1] += lazy[nod];
            lazy[nod] = 0;
        }
    }
    inline void update(int nod, int st, int dr, int a, int b, ll val){
        if(a <= st && dr <= b){
            lazy[nod] += val;
            push(nod);
            return;
        }
        push(nod);
        int mij = (st + dr) / 2;
        if(a <= mij)
            update(2 * nod, st, mij, a, b, val);
        if(b > mij)
            update(2 * nod + 1, mij + 1, dr, a, b, val);
        Arb[nod] = max(Arb[2 * nod], Arb[2 * nod + 1]);
    }
    inline ll query(int nod, int st, int dr, int a, int b){
        push(nod);
        if(a <= st && dr <= b)
            return Arb[nod];
        int mij = (st + dr) / 2;
        ll rez1 = 0, rez2 = 0;
        if(a <= mij)
            rez1 = query(2 * nod, st, mij, a, b);
        if(b > mij)
            rez2 = query(2 * nod + 1, mij + 1, dr, a, b);
        return max(rez1, rez2);
    }
} interv[NMAX];

inline int getC(int nod)
{
    viz[nod] = 1;
    sz[nod] = 1;
    int maxx = 0;
    for(auto it: G[nod])
        if(!viz[it.first] && mark[it.first])
        {
            int c = getC(it.first);
            if(c != -1)
                return c;
            sz[nod] += sz[it.first];
            maxx = max(maxx, sz[it.first]);
        }
    maxx = max(maxx, dim - sz[nod]);
    if(maxx <= dim / 2)
        return nod;
    return -1;
}

inline void DFS(int nod)
{
    viz[nod] = 1;
    tip[nod] = cnt;
    for(auto it: G[nod])
        if(!viz[it.first] && mark[it.first])
            DFS(it.first);
}

inline void buildTree(int nod, int tata = -1)
{
    interv[baza].in[id[nod]] = ++mov;
    for(auto it: G[nod])
        if(tata != it.first && mark[it.first])
        {
            mp[ {min(it.first, nod), max(it.first, nod)}].push_back({id[it.first], baza});
            dist[mov + 1] = dist[interv[baza].in[id[nod]]] + it.second;
            buildTree(it.first, nod);
        }
    interv[baza].out[id[nod]] = mov;
}

inline void centroidDecomp(vector<int> nodes)
{
    if(nodes.size() == 1)
        return;
    int mr = 0;
    for(auto it: nodes)
        mark[it] = 1, sz[it] = tip[it] = 0, viz[it] = 0, id[it] = ++mr;

    dim = nodes.size();
    int cen = getC(nodes[0]);
    baza = cen;
    mov = dist[1] = 0;
    interv[baza].init(nodes.size());
    buildTree(cen);
    interv[baza].build(1, 1, nodes.size());

    for(auto it: nodes)
        viz[it] = 0;
    viz[cen] = 1;
    cnt = 0;
    for(auto it: G[cen])
        if(!viz[it.first] && mark[it.first])
        {
            frati[cen].push_back(id[it.first]);
            ++cnt;
            DFS(it.first);
        }
    vector<vector<int> > nex(cnt + 1);
    for(auto it: nodes)
        nex[tip[it]].push_back(it);

    for(auto it: nodes)
        mark[it] = 0, sz[it] = tip[it] = 0, viz[it] = 0;
    int nn = cnt;
    for(int i = 1; i <= nn; ++i)
        centroidDecomp(nex[i]);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, q;
    ll w;
    cin >> n >> q >> w;

    vector<tuple<int, int, ll> > Muchie;
    for(int i = 1; i < n; ++i)
    {
        int a, b;
        ll c;
        cin >> a >> b >> c;
        Muchie.push_back(make_tuple(min(a, b), max(a, b), c));
        G[a].push_back({b, c});
        G[b].push_back({a, c});
    }

    vector<int> noduri;
    for(int i = 1; i <= n; ++i)
        noduri.push_back(i);
    centroidDecomp(noduri);

    auto calc = [](int i)
    {
        vector<ll> vec;
        for(auto it: frati[i])
        {
            ll val = interv[i].query(1, 1, interv[i].cati, interv[i].in[it], interv[i].out[it]);
            vec.push_back(val);
        }
        sort(vec.begin(), vec.end(), greater<ll>());
        ll maxxx = 0;
        if(vec.size() > 1)
            maxxx = vec[0] + vec[1];
        else maxxx = vec[0];
        return maxxx;
    };

    multiset<ll> s;
    for(int i = 1; i <= n; ++i)
        if(frati[i].size())
            maxx[i] = calc(i), s.insert(-maxx[i]);
    ll last = 0;
    for(int i = 1; i <= q; ++i)
    {
        int d;
        ll e;
        cin >> d >> e;
        d = (d + last) % (n - 1);
        e = (e + last) % w;

        int x, y;
        ll c;
        tie(x, y, c) = Muchie[d];
        for(auto it: mp[ {x, y}]){
            interv[it.second].update(1, 1, interv[it.second].cati, interv[it.second].in[it.first], interv[it.second].out[it.first], e - c);
            s.erase(s.find(-maxx[it.second]));
            maxx[it.second] = calc(it.second);
            s.insert(-maxx[it.second]);
        }
        Muchie[d] = make_tuple(x, y, e);
        cout << -*s.begin() << '\n';
        last = -*s.begin();
    }
    return 0;
}

Subtask #1
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	15180 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #2
0 / 13.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	8 ms	15180 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #3
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	15192 KB	Output is correct
2	Correct	8 ms	15180 KB	Output is correct
3	Correct	10 ms	15204 KB	Output is correct
4	Correct	35 ms	15356 KB	Output is correct
5	Correct	138 ms	16360 KB	Output is correct
6	Correct	8 ms	15180 KB	Output is correct
7	Correct	10 ms	15320 KB	Output is correct
8	Correct	18 ms	15396 KB	Output is correct
9	Correct	97 ms	15416 KB	Output is correct
10	Correct	887 ms	15628 KB	Output is correct
11	Correct	4427 ms	16692 KB	Output is correct
12	Correct	26 ms	17128 KB	Output is correct
13	Correct	138 ms	17100 KB	Output is correct
14	Correct	1256 ms	17152 KB	Output is correct
15	Execution timed out	5074 ms	17428 KB	Time limit exceeded
16	Halted	0 ms	0 KB	-