oj.uz

Submission #49428

# Submission time Handle Problem Language Result Execution time Memory
49428 2018-05-28T18:18:06 Z SpaimaCarpatilor City (JOI17_city) C++17
30 / 100
 583 ms 60880 KB 
#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]);
    }
}

#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16384 KB Output is correct
2 Correct 11 ms 16384 KB Output is correct
3 Correct 12 ms 16384 KB Output is correct
4 Correct 11 ms 16328 KB Output is correct
5 Correct 12 ms 16384 KB Output is correct
6 Correct 10 ms 16216 KB Output is correct
7 Correct 11 ms 16328 KB Output is correct
8 Correct 11 ms 16384 KB Output is correct
9 Correct 11 ms 16384 KB Output is correct
10 Correct 11 ms 16384 KB Output is correct
11 Correct 12 ms 16384 KB Output is correct
12 Correct 11 ms 16384 KB Output is correct

Subtask #2
22.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 23424 KB Output is correct - L = 174506050
2 Correct 192 ms 23280 KB Output is correct - L = 174256748
3 Correct 193 ms 23280 KB Output is correct - L = 174506050
4 Correct 192 ms 23536 KB Output is correct - L = 174506050
5 Partially correct 576 ms 59168 KB Output is partially correct - L = 31250125000
6 Partially correct 579 ms 59400 KB Output is partially correct - L = 31250125000
7 Partially correct 583 ms 59248 KB Output is partially correct - L = 31250125000
8 Partially correct 566 ms 58720 KB Output is partially correct - L = 31250125000
9 Partially correct 486 ms 60512 KB Output is partially correct - L = 31250125000
10 Partially correct 498 ms 60480 KB Output is partially correct - L = 31250125000
11 Partially correct 483 ms 60712 KB Output is partially correct - L = 31250125000
12 Partially correct 530 ms 60880 KB Output is partially correct - L = 31250125000
13 Partially correct 523 ms 59904 KB Output is partially correct - L = 31250125000
14 Partially correct 552 ms 59712 KB Output is partially correct - L = 31250125000
15 Correct 193 ms 23440 KB Output is correct - L = 174506050
16 Correct 194 ms 23408 KB Output is correct - L = 174506050
17 Correct 199 ms 23280 KB Output is correct - L = 174506050
18 Partially correct 544 ms 59656 KB Output is partially correct - L = 31250125000
19 Partially correct 542 ms 59544 KB Output is partially correct - L = 31250125000
20 Partially correct 548 ms 59616 KB Output is partially correct - L = 31250125000
21 Partially correct 540 ms 59616 KB Output is partially correct - L = 31250125000
22 Partially correct 573 ms 59624 KB Output is partially correct - L = 31250125000
23 Partially correct 533 ms 59320 KB Output is partially correct - L = 31250125000
24 Partially correct 551 ms 59608 KB Output is partially correct - L = 31250125000
25 Partially correct 573 ms 59368 KB Output is partially correct - L = 31250125000
26 Partially correct 549 ms 59088 KB Output is partially correct - L = 31250125000
27 Partially correct 557 ms 58944 KB Output is partially correct - L = 31250125000