Submission #47409

#	Time	Username	Problem	Language	Result	Execution time	Memory
47409		daniel_02	Construction of Highway (JOI18_construction)	C++17	16 / 100	240 ms	956 KiB

construction

#include <bits/stdc++.h>

#define ll long long
#define pb push_back
#define ppb pop_back
#define pf push_front
#define ppf pop_front

using namespace std;

const int N = 4000 + 7;
const int inf = 4000+7;

int a[N], pr[N];
int t[N];
int cnt;


deque<int>dq;

void update (int r) {
    for (; r > 0; r -= (r & -r))
        t[r] ++;
}
int get (int r) {
    int res = 0;
    for (; r < N; r += (r & -r))
        res += t[r];
    return res;
}
void dfs(int v)
{
    while (v != 0) {
        dq.pf(a[v]);
        v = pr[v];
    }
}
void conquer(int v)
{
    ll ans = 0;
    dfs(v);

    cnt = 1;
    for (int i = 0; i < dq.size(); i++)
    {
        ans += get(dq[i] + 1);
        update(dq[i]);
    }
//    for (int i = 0; i < dq.size(); i++)
//        update(1, 1, inf, dq[i], -inf);
    memset(t, 0, sizeof(t));
    dq.clear();
    printf("%lld\n", ans);
}
void upd(int v, int x)
{
   while (v != 0) {
        a[v] = x;
        v = pr[v];
   }
}
vector <int> vec;

main()
{
    int n;

    scanf("%d", &n);

    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        vec.pb(a[i]);
    }
    sort(vec.begin(),vec.end());
    vec.erase(unique(vec.begin(),vec.end()),vec.end());

    for (int i = 1; i <= n; i ++) {
        a[i] = lower_bound(vec.begin(),vec.end(),a[i]) - vec.begin() + 1;
    }

    for (int i = 1; i < n; i++)
    {
        int q, w;
        scanf("%d%d", &q, &w);
        if (i == 1)
        {
            puts("0");
            pr[w] = q;
            a[q] = a[w];
            continue;
        }
        conquer(q);
        upd(q, a[w]);
        pr[w] = q;
    }
}

Compilation message (stderr)

construction.cpp: In function 'void conquer(int)':
construction.cpp:44:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < dq.size(); i++)
                     ~~^~~~~~~~~~~
construction.cpp: At global scope:
construction.cpp:64:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
construction.cpp: In function 'int main()':
construction.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:71:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
construction.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &q, &w);
         ~~~~~^~~~~~~~~~~~~~~~

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