Submission #523362

#	Time	Username	Problem	Language	Result	Execution time	Memory
523362		CPSC	Construction of Highway (JOI18_construction)	C++14	16 / 100	2086 ms	28928 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;
vector < 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;
        vv.pb({c[b],x});
        for (int i = 0; i < vec[lst].size(); i++) {
            if (vec[lst][i].s + sum > x) {
                vv.pb({vec[lst][i].f,vec[lst][i].s - (x - sum)});
                idx = i + 1;
                break;
            }
            sum += vec[lst][i].s;
            idx = i + 1;
            if (sum == x) break;
        }
        
        for (int i = idx; i < vec[lst].size(); i++) {
            vv.pb({vec[lst][i].f,vec[lst][i].s});
        }
        vec[lst].clear();
        for (int i = 0; i < vv.size(); i++) {
            if (!vec[lst].size()) vec[lst].pb(vv[i]);
            else {
                if (vec[lst].back().f == vv[i].f) vec[lst].back().s += vv[i].s;
                else vec[lst].pb({vv[i].f,vv[i].s});
            }
        }
        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::vector<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:118: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]
  118 |         for (int i = 0; i < vec[lst].size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
construction.cpp:129:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int i = idx; i < vec[lst].size(); i++) {
      |                           ~~^~~~~~~~~~~~~~~~~
construction.cpp:133: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]
  133 |         for (int i = 0; i < vv.size(); i++) {
      |                         ~~^~~~~~~~~~~
construction.cpp: At global scope:
construction.cpp:144:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  144 | main() {
      | ^~~~
construction.cpp: In function 'int main()':
construction.cpp:155:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |     for (int i = 1; i < tocomp.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~

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