Submission #523365

#	Time	Username	Problem	Language	Result	Execution time	Memory
523365		CPSC	Construction of Highway (JOI18_construction)	C++14	100 / 100	388 ms	93800 KiB

construction

# include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define pii pair <int, int >
using namespace std;
const int N = 1e5 + 5;
int lv[N],sz[N],par[N],tree[N],in[N],out[N],tin,sizeofchain[N];
map <int, int> shes;
vector <int> v[N],tocomp;
deque < pii > vec[N];
int bigchild[N],chain[N],n,a[N],b[N],c[N];
void update(int idx, int val) {
    for (int i = idx; i < N; i += i&(-i)) {
        tree[i] += val;
    }
}
int getans(int idx) {
    int pas = 0;
    for (int i = idx; i > 0; i-=i&(-i)) {
        pas += tree[i];
    }
    return pas;
}
void dfs(int a, int p) {
    sz[a] = 1;
    lv[a] = lv[p] + 1;
    par[a] = p;
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (to == p) continue;
        dfs(to,a);
        sz[a] += sz[to];
        if (!bigchild[a] || sz[bigchild[a]] < sz[to]) {
            bigchild[a] = to;
        }
    }
}
void dfs1(int a, int p) {
    tin++;
    in[a] = tin;
    if (bigchild[a]) dfs1(bigchild[a],a);
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (to == p || to == bigchild[a]) continue;
        dfs1(to,a);
    }
    out[a] = tin;
}
void dfs_chain(int a,int p) {
    if (bigchild[a]) {
        chain[bigchild[a]] = chain[a];
    }
    sizeofchain[a]++;
    if (!vec[chain[a]].size()) {
        vec[chain[a]].pb({c[a],1});
    } else {
        if (vec[chain[a]].back().f == c[a]) {
            vec[chain[a]].back().s++;
        } else vec[chain[a]].pb({c[a],1});
    }
    for (int i = 0; i < v[a].size(); i++) {
        int to = v[a][i];
        if (to == p) continue;
        dfs_chain(to,a);
    }
}
int getans(int a, int b) {
    int ans = 0;
    int lst = chain[a];
    int cur = a;
    vector <pii> pas;
    //if (a == 2 && b == 3) cout<<lst<<"\n",prnt(vec[lst]);
    while (true) {
        lst = chain[cur];
        int x = lv[cur] - lv[lst] + 1;
        //if (a == 5 && b == 9) cout<<lst<<" "<<cur<<endl;
        vector <pii> vv;
        int sum = 0;
        for (int i = 0; i < vec[lst].size(); i++) {
            if(vec[lst][i].s + sum > x) {
               // if (a == 5 && b == 9 && lst == 1) cout<<x<<" "<<sum<<" "<< (x - sum)<<endl;
                vv.pb({vec[lst][i].f, (x - sum)});
                break;
            } 
            
            sum += vec[lst][i].s;
            vv.pb({vec[lst][i].f,vec[lst][i].s});
            if (sum == x) break;
        }
        reverse(vv.begin(),vv.end());
        for (int i = 0; i < vv.size(); i++) {
            pas.pb({vv[i].f,vv[i].s});
        }
        cur = par[lst];
        if (cur == 0) break;
    }
    //if (a == 2 && b == 3)cout<<endl<<endl,
    //prnt(pas);
   // cout<<a<<"   "<<b<<endl;
   // prnt(pas);
    for (int i = 0; i < pas.size(); i++) {
        ans += getans(pas[i].f - 1)*pas[i].s;
        update(pas[i].f, pas[i].s);
    }
    for (int i = 0; i < pas.size(); i++) update(pas[i].f, -pas[i].s);
    return ans;
}
void toadd(int a, int b) {
    int lst = chain[a];
    int cur = a;
    while (true) {
        lst = chain[cur];
        int x = lv[cur] - lv[lst] + 1;
        int sum = 0; int idx = 0;
        vector <pii> vv;
        
        while (vec[lst].size()) {
            int i = 0;
            if (vec[lst][i].s + sum > x) {
                vec[lst][i].s = vec[lst][i].s - (x - sum);
                break;
            }
            sum += vec[lst][i].s;
            vec[lst].pop_front();
            if (sum == x) break;
        }
        vec[lst].push_front({c[b],x});
        cur = par[lst];
        if (cur == 0) break;
    }
}
main() {
	std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	#define endl '\n'
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>c[i];
        tocomp.pb(c[i]);
    }
    sort(tocomp.begin(),tocomp.end());
    int cnt = 1;
    shes[tocomp[0]] = 1;
    for (int i = 1; i < tocomp.size(); i++) {
        if (tocomp[i] != tocomp[i - 1]) cnt++;
        shes[tocomp[i]] = cnt;
    }
    for (int i = 1; i <= n; i++) c[i] = shes[c[i]];
    for (int i = 1; i <= n - 1; i++) {
        cin>>a[i]>>b[i];
        v[a[i]].pb(b[i]);
        v[b[i]].pb(a[i]);
    }
    for (int i = 1; i <= n; i++) {
        chain[i] = i;
    }
    dfs(1,0);
    dfs1(1,0);
    dfs_chain(1,0);
    for (int i = 1; i <= n - 1; i++) {
        int ss  = getans(a[i],b[i]);
        toadd(a[i],b[i]);
        cout<<ss<<endl;
    }
}

Compilation message (stderr)

construction.cpp: In function 'void dfs(int, int)':
construction.cpp:29:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
construction.cpp: In function 'void dfs1(int, int)':
construction.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
construction.cpp: In function 'void dfs_chain(int, int)':
construction.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < v[a].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
construction.cpp: In function 'int getans(int, int)':
construction.cpp:80:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int i = 0; i < vec[lst].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
construction.cpp:92:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int i = 0; i < vv.size(); i++) {
      |                         ~~^~~~~~~~~~~
construction.cpp:102:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |     for (int i = 0; i < pas.size(); i++) {
      |                     ~~^~~~~~~~~~~~
construction.cpp:106:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |     for (int i = 0; i < pas.size(); i++) update(pas[i].f, -pas[i].s);
      |                     ~~^~~~~~~~~~~~
construction.cpp: In function 'void toadd(int, int)':
construction.cpp:115:26: warning: unused variable 'idx' [-Wunused-variable]
  115 |         int sum = 0; int idx = 0;
      |                          ^~~
construction.cpp: At global scope:
construction.cpp:133:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  133 | main() {
      | ^~~~
construction.cpp: In function 'int main()':
construction.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |     for (int i = 1; i < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~

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