Submission #312689

#	Time	Username	Problem	Language	Result	Execution time	Memory
312689		YJU	Construction of Highway (JOI18_construction)	C++14	100 / 100	357 ms	8688 KiB

construction

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector")
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
const ll MOD=1e9+7;
const ll MOD2=998244353;
const ll K=350;
const ld pi=3.14159265359;
const ll INF=(1LL<<40);
#define SQ(i) ((i)*(i))
#define REP(i,n) for(ll i=0;i<n;i++)
#define REP1(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define setp setprecision
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

const int N = 1e5 + 7;

struct LCT {
    int f[N], ch[N][2], s[N], z[N], a[N];
    #define lc ch[p][0]
    #define rc ch[p][1]
    #define upd(p) s[p] = s[ch[p][0]] + s[ch[p][1]] + 1
    #define get(p) (p == ch[f[p]][1])
    #define rev(p) v[p] ^= 1, swap(ch[p][0], ch[p][1])
    #define isrt(p) (ch[f[p]][0] != p && ch[f[p]][1] != p)
    inline void spd(int p) {
        if (z[p]) {
            if (lc) a[lc] = z[lc] = z[p];
            if (rc) a[rc] = z[rc] = z[p];
            z[p] = 0;
        }
    }
    inline void rot(int p) {
        int x = f[p], y = f[x], u = get(p), v = get(x), o = isrt(x);
        f[ch[p][u^1]] = x, ch[x][u] = ch[p][u^1];
        f[x] = p, ch[p][u^1] = x, upd(x), upd(p);
        if ((f[p] = y) && !o) ch[y][v] = p;
    }
    void pre(int p) {
        if (!isrt(p)) pre(f[p]);
        spd(p);
    }
    inline void splay(int p) {
        pre(p);
        for (int x = f[p]; !isrt(p); rot(p), x = f[p])
            if (!isrt(x)) rot(get(p) == get(x) ? x : p);
    }
    inline vector<pll> access(int p) {
        vector<pll> ret;
        int w = 0;
        for (int x = 0; p; p = f[x=p])
            splay(p), rc = x, upd(p),
            ret.pb(mp(a[p], s[p] - w)), w = s[p];
        return ret;
    }
    inline void link(int p, int x) {
        int w = a[x];
        splay(p), rc = x, f[x] = p, splay(x), upd(x), a[x] = z[x] = w;
    }
} lct;

struct BIT {
    vector<ll> c;
    inline BIT() {}
    inline BIT(int n) { c.resize(n); }
    inline void add(ll x, ll k) {
        while (x < c.size()) c[x] += k, x += x & -x;
    }
    inline ll ask(ll x) {
        ll k = 0;
        while (x) k += c[x], x -= x & -x;
        return k;
    }
};

int n, a[N];

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n;
    for (int i = 1; i <= n; i++) cin>>a[i], lct.a[i] = a[i];
    sort(a + 1, a + n + 1);
    int t = unique(a + 1, a + n + 1) - (a + 1);
    BIT c(t + 1);
    for (int i = 1; i <= n; i++)
        lct.a[i] = lower_bound(a + 1, a + t + 1, lct.a[i]) - a;
    lct.s[1] = 1;
    for (int i = 1, x, y; i < n; i++) {
    	cin>>x>>y;
        auto ret = lct.access(x);
        ll ans = 0;
        for (pll o : ret)
            ans += o.se * c.ask(o.fi - 1), c.add(o.fi, o.se);
            cout<<ans<<"\n";
        for (pll o : ret) c.add(o.fi, -o.se);
        lct.link(x, y);
    }
    return 0;
}

Compilation message (stderr)

construction.cpp: In member function 'void BIT::add(ll, ll)':
construction.cpp:74:18: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |         while (x < c.size()) c[x] += k, x += x & -x;
      |                ~~^~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:99:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   99 |         for (pll o : ret)
      |         ^~~
construction.cpp:101:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  101 |             cout<<ans<<"\n";
      |             ^~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84