Submission #49892

#	Time	Username	Problem	Language	Result	Execution time	Memory
49892		daniel_02	Construction of Highway (JOI18_construction)	C++17	16 / 100	735 ms	16196 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;
struct con
{
    con * l; con * r;

    int cnt;

    con()
    {
        l = NULL; r = NULL;
        cnt = 0;
    }
};
con * root;

ll create_and_get(int x)
{
    con * cur = root;
    ll ans = 0;
    for (int i = 25; i >= 0; i--)
    {
        if (x & (1 << i))
        {
            if (cur -> r == NULL)cur -> r = new con();

            cur = cur -> r;
        }
        else
        {
            if (cur -> l == NULL)cur -> l = new con();

            if (cur -> r != NULL)ans += cur -> r -> cnt;

            cur = cur -> l;
        }
        cur -> cnt ++;
    }

    return ans;
}

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;
    root = new con();

    for (int i = 0; i < dq.size(); i++)
    {
        ans += create_and_get(dq[i]);
    }

    delete root;
//    for (int i = 0; i < dq.size(); i++)
//        update(1, 1, inf, dq[i], -inf);
    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:72: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:92:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
construction.cpp: In function 'int main()':
construction.cpp:96:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
construction.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
construction.cpp:112: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