oj.uz

Submission #27285

# Submission time Handle Problem Language Result Execution time Memory
27285 2017-07-12T07:04:20 Z 상수조아(#1141) City (JOI17_city) C++11
30 / 100
 596 ms 56736 KB 
#include "Encoder.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

vector <int> E[250010];
int tm, S[250050], D[250050];

void dfs(int x, int fa) {
    S[x] = ++tm;
    for(int e : E[x]) if(e != fa) dfs(e, x);
    D[x] = tm;
}

ll sq(int x) { return (ll)x * (x+1) / 2; }

ll get(int s, int d) {
    --s; --d;
    return sq(250000) - sq(250000-s) + (d-s);
}

void Encode(int N, int A[], int B[])
{
    rep(i, N-1) E[A[i]].pb(B[i]), E[B[i]].pb(A[i]);
    dfs(0, -1);
    rep(i, N) Code(i, get(S[i], D[i]));
}

#include "Device.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

ll A[250050];

void InitDevice()
{
    for(int i=1;i<=250000;i++) A[i] = A[i-1] + (250001 - i);
}

pii get(ll X) {
    int s = (int)(upper_bound(A+1, A+250001, X) - A - 1);
    int d = s + (X - A[s]);
    return pii(s, d);
}

int Answer(long long S, long long T)
{
    pii ps = get(S);
    int sx = ps.Fi, sy = ps.Se;
    pii pt = get(T);
    int tx = pt.Fi, ty = pt.Se;
    if(sx <= tx && ty <= sy) return 1;
    if(tx <= sx && sy <= ty) return 0;
    return 2;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
22.0 / 92.0

# Verdict Execution time Memory Grader output
1 Correct 194 ms 19440 KB Output is correct - L = 174506049
2 Correct 199 ms 19440 KB Output is correct - L = 174256747
3 Correct 199 ms 19680 KB Output is correct - L = 174506049
4 Correct 195 ms 19440 KB Output is correct - L = 174506049
5 Partially correct 588 ms 55512 KB Output is partially correct - L = 31250124999
6 Partially correct 580 ms 55280 KB Output is partially correct - L = 31250124999
7 Partially correct 575 ms 55264 KB Output is partially correct - L = 31250124999
8 Partially correct 580 ms 54920 KB Output is partially correct - L = 31250124999
9 Partially correct 502 ms 56544 KB Output is partially correct - L = 31250124999
10 Partially correct 482 ms 56632 KB Output is partially correct - L = 31250124999
11 Partially correct 499 ms 56536 KB Output is partially correct - L = 31250124999
12 Partially correct 549 ms 56736 KB Output is partially correct - L = 31250124999
13 Partially correct 557 ms 56040 KB Output is partially correct - L = 31250124999
14 Partially correct 579 ms 55712 KB Output is partially correct - L = 31250124999
15 Correct 197 ms 19440 KB Output is correct - L = 174506049
16 Correct 195 ms 19448 KB Output is correct - L = 174506049
17 Correct 197 ms 19440 KB Output is correct - L = 174506049
18 Partially correct 551 ms 55720 KB Output is partially correct - L = 31250124999
19 Partially correct 538 ms 55768 KB Output is partially correct - L = 31250124999
20 Partially correct 540 ms 55656 KB Output is partially correct - L = 31250124999
21 Partially correct 544 ms 55952 KB Output is partially correct - L = 31250124999
22 Partially correct 561 ms 55776 KB Output is partially correct - L = 31250124999
23 Partially correct 531 ms 55480 KB Output is partially correct - L = 31250124999
24 Partially correct 536 ms 55280 KB Output is partially correct - L = 31250124999
25 Partially correct 562 ms 55288 KB Output is partially correct - L = 31250124999
26 Partially correct 596 ms 55200 KB Output is partially correct - L = 31250124999
27 Partially correct 590 ms 55144 KB Output is partially correct - L = 31250124999