Submission #49428

#	Time	Username	Problem	Language	Result	Execution time	Memory
49428		SpaimaCarpatilor	City (JOI17_city)	C++17	30 / 100	583 ms	60880 KiB

Encoder

#include "Encoder.h"
#include<bits/stdc++.h>
using namespace std;

const int maxN = 250000;
int nr = 0, l[250009], r[250009];
long long partialS[250009];
vector < int > v[250009];

void dfs (int nod, int tata)
{
    l[nod] = ++nr;
    for (auto it : v[nod])
        if (it != tata)
            dfs (it, nod);
    r[nod] = nr;
}

void Encode (int N, int A[], int B[])
{
    for (int i=0; i<N - 1; i++)
        v[A[i]].push_back (B[i]),
        v[B[i]].push_back (A[i]);
    dfs (0, -1);
    partialS[0] = 0;
    for (int i=1; i<=maxN; i++)
        partialS[i] = partialS[i - 1] + maxN - i + 1;
	for (int i=0; i<N; i++)
    {
        r[i] -= l[i], r[i] ++;
		Code(i, partialS[l[i] - 1] + r[i]);
    }
}

Device

#include "Device.h"
#include<bits/stdc++.h>
using namespace std;

const int maxN = 250000;
static long long partialS[maxN + 2];

void InitDevice()
{
    partialS[0] = 0;
    for (int i=1; i<=maxN; i++)
        partialS[i] = partialS[i - 1] + maxN - i + 1;
}

void decode (long long X, int &i, int &j)
{
    int p = 0, u = maxN - 1, mij;
    while (p <= u)
    {
        mij = (p + u) >> 1;
        if (partialS[mij] < X) i = mij + 1, p = mij + 1;
        else u = mij - 1;
    }
    j = X - partialS[i - 1], j += i - 1;
}

int Answer (long long S, long long T)
{
    int lS, rS; decode (S, lS, rS);
    int lT, rT; decode (T, lT, rT);
    if (lT <= lS && rS <= rT) return 0;
    if (lS <= lT && rT <= rS) return 1;
	return 2;
}

Compilation message (stderr)

Encoder.cpp: In function 'void Encode(int, int*, int*)':
Encoder.cpp:26:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
     for (int i=1; i<=maxN; i++)
     ^~~
Encoder.cpp:28:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  for (int i=0; i<N; i++)
  ^~~

Device.cpp: In function 'int Answer(long long int, long long int)':
Device.cpp:24:24: warning: 'lT' may be used uninitialized in this function [-Wmaybe-uninitialized]
     j = X - partialS[i - 1], j += i - 1;
                      ~~^~~
Device.cpp:30:9: note: 'lT' was declared here
     int lT, rT; decode (T, lT, rT);
         ^~
Device.cpp:32:5: warning: 'lS' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if (lS <= lT && rT <= rS) return 1;
     ^~

• Subtask 1: 8 / 8
• Subtask 2: 22 / 92