oj.uz

Submission #1031004

# Submission time Handle Problem Language Result Execution time Memory
1031004 2024-07-22T13:25:56 Z Antekb JOI tour (JOI24_joitour) C++17
6 / 100
 1235 ms 421564 KB 
#include "bits/stdc++.h"	/** keep-include */
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

#include "joitour.h"

const int N=2e5+5;

ll result;
int typ[N];


struct drzewo{
    vi real_name;
    vi siz, par, pre, post, subtree, order;
    vector<vi> E;
    int root=-1, real_root;
    int n;
    vi ile[2];
    vector<ll> sum[2];
    ll iles[2]={}, sums[2]={};
    ll zle=0;
    ll res=0;
    int new_name(int v){
        return lower_bound(all(real_name), v)-real_name.begin();
    }
    void dfs_cent(int v){
        siz[v]=1;
        bool ok=1;
        for(int u:E[v]){
            if(u!=par[v]){
                par[u]=v;
                dfs_cent(u);
                siz[v]+=siz[u];
                if(siz[u]*2>n)ok=0;
            }
        }
        if(ok && 2*(n-siz[v])<=n){
            root=v;
        }
    }
    void dfs_init(int v, int sub=-1){
        deb(v, sub, order, root, E[v]);
        pre[v]=order.size();
        order.pb(v);
        int cnt=0;
        if(v!=root){
            subtree[v]=sub;
            for(int &u:E[v])if(u==par[v])swap(u, E[v].back());
            E[v].pop_back();
        }
        for(int u:E[v]){
            par[u]=v;
            if(v==root)dfs_init(u, cnt);
            else dfs_init(u, sub);
            cnt++;
        }
        post[v]=order.size();
    }
    pair<int, ll> licz(int v, int lbl, int num){//num - liczba 1
        pair<int, ll> a;
        for(int u:E[v]){
            auto b=licz(u, lbl, num+(typ[real_name[v]]==1));
            a.st+=b.st;
            a.nd+=b.nd;
        }
        if(typ[real_name[v]]==lbl*2){
            a.st++;
            a.nd+=num;
        }
        return a;
    }
    void calc(){
        result-=res;
        res=0;
        iles[0]=0;
        iles[1]=0;
        sums[0]=0;
        sums[1]=0;
        zle=0;
        for(int i=0; i<E[root].size(); i++){
            auto a=licz(E[root][i], 0, 0);
            auto b=licz(E[root][i], 1, 0);
            ile[0][i]={a.st};
            ile[1][i]={b.st};
            sum[0][i]={a.nd};
            sum[1][i]={b.nd};
            iles[0]+=a.st;
            iles[1]+=b.st;
            sums[0]+=a.nd;
            sums[1]+=b.nd;
            res-=a.st*b.nd;
            res-=a.nd*b.st;
            zle+=a.st*1ll*b.st;
        }
        res+=sums[0]*iles[1];
        res+=sums[1]*iles[0];
        if(typ[real_name[root]]==1)res+=iles[0]*1ll*iles[1]-zle;
        else res+=sums[1-typ[real_name[root]]/2];
        result+=res;
    }
    drzewo(vi V, vector<pii> edges){
        deb(V, edges);
        real_name=V;
        sort(all(real_name));
        n=real_name.size();
        E.resize(n);
        siz.resize(n);
        par.resize(n);
        subtree.resize(n);
        pre.resize(n);
        post.resize(n);
        par[0]=-1;
        for(auto &[u, v] : edges){
            deb(u, v, real_name);
            u=new_name(u);
            v=new_name(v);
            E[u].pb(v);
            E[v].pb(u);
        }
        dfs_cent(0);
        assert(root!=-1);
        deb(root, real_name);
        real_root=real_name[root];
        par[root]=-1;
        ile[0].resize(E[root].size());
        ile[1].resize(E[root].size());
        sum[0].resize(E[root].size());
        sum[1].resize(E[root].size());
        dfs_init(root);
        calc();
    }
    pair<vi, vector<pii> > prep(int v){
        vi vert;
        vector<pii> edg;
        for(int i=pre[v]; i<post[v]; i++){
            int u=order[i];
            vert.pb(real_name[u]);
            for(int w:E[u]){
                edg.pb(mp(real_name[u], real_name[w]));
            }
        }
        return {vert, edg};
    }
    void update_slow(){
        calc();
    }
    int licz_gora(int v){
        if(v==root)return 0;
        return licz_gora(par[v])+typ[real_name[v]]==1;
    }
    int licz_dol(int v, int lbl){
        int cnt=0;
        for(int i=pre[v]; i<post[v]; i++){
            if(typ[real_name[order[i]]]==lbl)cnt++;
        }
        return cnt;
    }
    void update_fast(int v, int stary, int nowy){
        v=new_name(v);
        deb(root, v, stary, nowy);
        deb(ile[0], ile[1], sum[0], sum[1]);
        result-=res;
        typ[real_name[v]]=stary;
        
        if(typ[real_name[root]]==1)res-=iles[0]*1ll*iles[1]-zle;
        else res-=sums[1-typ[real_name[root]]/2];
        
        if(v!=root){
            res-=sums[0]*iles[1];
            res-=sums[1]*iles[0];
            int sub=subtree[v];

            iles[0]-=ile[0][sub];
            iles[1]-=ile[1][sub];
            sums[0]-=sum[0][sub];
            sums[1]-=sum[1][sub];
            res+=ile[0][sub]*sum[1][sub];
            res+=ile[1][sub]*sum[0][sub];
            zle-=ile[1][sub]*1ll*ile[0][sub];

            if(stary==1){
                int cnt0=licz_dol(v, 0);
                int cnt2=licz_dol(v, 2);
                sum[0][sub]-=cnt0;
                sum[1][sub]-=cnt2;
            }
            else{
                int cnt=licz_gora(v);
                deb(cnt);
                sum[stary/2][sub]-=cnt;
                ile[stary/2][sub]--;
            }
            deb(ile[0], ile[1], sum[0], sum[1]);
    
            typ[real_name[v]]=nowy;
            
            if(nowy==1){
                int cnt0=licz_dol(v, 0);
                int cnt2=licz_dol(v, 2);
                sum[0][sub]+=cnt0;
                sum[1][sub]+=cnt2;
            }
            else{
                int cnt=licz_gora(v);
                sum[nowy/2][sub]+=cnt;
                ile[nowy/2][sub]++;
            }

            iles[0]+=ile[0][sub];
            iles[1]+=ile[1][sub];
            sums[0]+=sum[0][sub];
            sums[1]+=sum[1][sub];
            res-=ile[0][sub]*sum[1][sub];
            res-=ile[1][sub]*sum[0][sub];
            zle+=ile[1][sub]*1ll*ile[0][sub];
            
            res+=sums[0]*iles[1];
            res+=sums[1]*iles[0];
        }
        typ[real_name[v]]=nowy;
        if(typ[real_name[root]]==1)res+=iles[0]*1ll*iles[1]-zle;
        else res+=sums[1-typ[real_name[root]]/2];
        result+=res;
        deb(root, v, stary, nowy);
        deb(ile[0], ile[1], sum[0], sum[1]);
    }
};

vector<drzewo*> drzewa(N);
int rodzic[N];

void stworz(vector<int> vert, vector<pii> edg, int par){
    drzewo* T=new drzewo(vert, edg);
    drzewa[T->real_root]=T;
    deb(T->real_root);
    rodzic[T->real_root]=par;
    for(int u:T->E[T->root]){
        auto a = T->prep(u);
        deb(T->real_root, a.st, a.nd);
        stworz(a.st, a.nd, T->real_root);
    }
}

int n;

void init(int _n, std::vector<int> F, std::vector<int> U, std::vector<int> V,
          int Q) {
    n=_n;
    vector<pii> edges;
    for(int i=0; i<n-1; i++){
        edges.pb(mp(U[i], V[i]));   
    }
    for(int i=0; i<n; i++){
        typ[i]=F[i];
    }
    vi v(n);
    iota(all(v), 0);
    stworz(v, edges, -1);
}

void change(int X, int Y) {
    int stary=typ[X];
    int v=X;
    typ[X]=Y;
    while(X!=-1){
        drzewa[X]->update_fast(v, stary, Y);
        X=rodzic[X];
    }
}

long long num_tours() {
  return result;
}

Compilation message

joitour.cpp:17:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
joitour.cpp:17:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
joitour.cpp:17:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
joitour.cpp:19:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
joitour.cpp:19:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~
joitour.cpp: In member function 'void drzewo::calc()':
joitour.cpp:105:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |         for(int i=0; i<E[root].size(); i++){
      |                      ~^~~~~~~~~~~~~~~

Subtask #1
0.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Incorrect 1 ms 1880 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Incorrect 1 ms 1880 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1091 ms 403804 KB Output is correct
3 Correct 1147 ms 403552 KB Output is correct
4 Correct 1233 ms 403448 KB Output is correct
5 Correct 1235 ms 404020 KB Output is correct
6 Correct 794 ms 387672 KB Output is correct
7 Correct 817 ms 387668 KB Output is correct
8 Correct 1217 ms 391632 KB Output is correct
9 Correct 1120 ms 387644 KB Output is correct
10 Correct 1028 ms 371404 KB Output is correct
11 Correct 1025 ms 361552 KB Output is correct
12 Correct 1150 ms 397476 KB Output is correct
13 Correct 1098 ms 397480 KB Output is correct
14 Correct 1165 ms 397448 KB Output is correct
15 Correct 1144 ms 397348 KB Output is correct
16 Correct 1180 ms 420152 KB Output is correct
17 Correct 1 ms 1880 KB Output is correct
18 Correct 1 ms 1880 KB Output is correct
19 Correct 1 ms 1880 KB Output is correct
20 Correct 1 ms 1880 KB Output is correct
21 Correct 955 ms 338228 KB Output is correct
22 Correct 940 ms 335840 KB Output is correct
23 Correct 942 ms 340252 KB Output is correct
24 Correct 941 ms 340932 KB Output is correct
25 Correct 191 ms 156972 KB Output is correct
26 Correct 189 ms 156980 KB Output is correct
27 Correct 185 ms 156772 KB Output is correct
28 Correct 221 ms 156900 KB Output is correct
29 Correct 701 ms 421564 KB Output is correct
30 Correct 696 ms 421476 KB Output is correct
31 Correct 758 ms 421540 KB Output is correct
32 Correct 864 ms 421536 KB Output is correct
33 Correct 748 ms 390748 KB Output is correct
34 Correct 740 ms 391012 KB Output is correct
35 Correct 776 ms 390928 KB Output is correct
36 Correct 838 ms 390904 KB Output is correct

Subtask #4
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Correct 3 ms 1880 KB Output is correct
4 Incorrect 2 ms 1880 KB Wrong Answer [1]
5 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1880 KB Wrong Answer [1]
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Incorrect 1 ms 1880 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -

Subtask #7
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1880 KB Output is correct
2 Correct 1 ms 1880 KB Output is correct
3 Incorrect 1 ms 1880 KB Wrong Answer [1]
4 Halted 0 ms 0 KB -