oj.uz

Submission #108798

# Submission time Handle Problem Language Result Execution time Memory
108798 2019-05-02T07:07:56 Z tri Highway Tolls (IOI18_highway) C++14
13 / 100
 388 ms 17596 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = false;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"); }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;

ll ask(const vi &w);

void answer(int s, int t);

int N, M;
vi e1, e2;
ll A, B;
vector<vector<pi>> aList;
ll base;

vi query;

int searchE() {
    int low = 0;
    int high = M - 1;

    while (low != high) {
        int mid = (low + high) / 2;
        for (int i = 0; i < N; i++) {
            query[i] = i <= mid;
        }
        ll res = ask(query);
        if (res == base) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }
    return low;
}

vi dist[3];
int cT;

int fDist(int r) {
    queue<int> q;
    q.push(r);

    dist[cT][r] = 0;

    while (q.size()) {
        int cV = q.front();
        q.pop();
        for (pi aE : aList[cV]) {
            if (dist[cT][aE.f] == -1) {
                dist[cT][aE.f] = dist[cT][cV] + 1;
                q.push(aE.f);
            }
        }
    }
}

vi t, pE;

void bTree(int r, vi &mbr) {
    queue<int> q;
    q.push(r);

    for (int j = 0; j < N; j++) {
        dist[cT][j] = -1;
    }
    dist[cT][r] = 0;
    mbr.pb(r);

    while (q.size()) {
        int cV = q.front();
        q.pop();
        for (pi aE : aList[cV]) {
            if (t[aE.f] == cT && dist[cT][aE.f] == -1) {
                dist[cT][aE.f] = dist[cT][cV] + 1;
                mbr.pb(aE.f);
                query[aE.s] = 0;
                pE[aE.f] = aE.s;

                q.push(aE.f);
            }
        }
    }
}

bool cmp(int a, int b) {
    return dist[cT][a] < dist[cT][b];
}

int find(vi &mbr) {
    sort(mbr.begin(), mbr.end(), cmp);
    reverse(mbr.begin(), mbr.end());

    if (cT == 1) {
        ps("srtd");
        ps(mbr);
    }

    //decreasing dist
    int low = 0;
    int high = mbr.size() - 1;

    while (low != high) {
        int mid = (low + high) / 2;
        for (int i = 0; i < mbr.size(); i++) {
            int cE = pE[mbr[i]];
            if(cE >= 0){
                query[cE] = i <= mid;
            }
        }
        ll res = ask(query);
        if (res == base) {
            low = mid + 1;
        } else {
            high = mid;
        }
    }

    for (int i = 0; i < mbr.size(); i++) {
        int cE = pE[mbr[i]];
        if(cE >= 0){
            query[cE] = 0;
        }
    }
    return mbr[low];
}

void find_pair(int iN, vi ie1, vi ie2, int iA, int iB) {
    ps("start");
    N = iN;
    e1 = ie1, e2 = ie2;
    A = iA, B = iB;

    aList.resize(N);
    M = e1.size();
    for (int i = 0; i < M; i++) {
        aList[e1[i]].pb({e2[i], i});
        aList[e2[i]].pb({e1[i], i});
    }

    vi empty(M);
    for(int i = 0; i < M; i++){
        empty[i] = 0;
    }
    base = ask(empty);
    ps(base);

    query.resize(M);
    int split = searchE();
    ps("split", split, e1[split], e2[split]);

    dist[0].resize(N);
    dist[1].resize(N);
    for (int j = 0; j < N; j++) {
        dist[0][j] = -1;
        dist[1][j] = -1;
    }

    cT = 0;
    fDist(e1[split]);
    cT = 1;
    fDist(e2[split]);

    ps("dist");
    ps(dist[0]);
    ps(dist[1]);

    t.resize(N);
    pE.resize(N);
    for (int i = 0; i < N; i++) {
        pE[i] = -1;
    }
    for (int i = 0; i < N; i++) {
        t[i] = dist[0][i] > dist[1][i];
    }

    for (int i = 0; i < N; i++) {
        query[i] = 1;
    }
    query[split] = 0;

    vi mbrS, mbrT;
    cT = 0;
    bTree(ie1[split], mbrS);
    cT = 1;
    bTree(ie2[split], mbrT);

    ps("mbr");
    ps(mbrS);
    ps(mbrT);
    ps("query");
    ps(query);

    ps("pE");
    ps(pE);

    cT = 0;
    int s = find(mbrS);
    cT = 1;
    int t = find(mbrT);
    ps(s, t);
    answer(s, t);
}

Compilation message

highway.cpp: In function 'int fDist(int)':
highway.cpp:126:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
highway.cpp: In function 'int find(vi&)':
highway.cpp:175:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < mbr.size(); i++) {
                         ~~^~~~~~~~~~~~
highway.cpp:189:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < mbr.size(); i++) {
                     ~~^~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 404 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 22 ms 1412 KB Output is correct
3 Correct 272 ms 10760 KB Output is correct
4 Correct 248 ms 10716 KB Output is correct
5 Correct 253 ms 10728 KB Output is correct
6 Correct 250 ms 10724 KB Output is correct
7 Correct 256 ms 10724 KB Output is correct
8 Correct 242 ms 10720 KB Output is correct
9 Correct 254 ms 10724 KB Output is correct
10 Correct 243 ms 10720 KB Output is correct
11 Correct 288 ms 10000 KB Output is correct
12 Correct 259 ms 10084 KB Output is correct
13 Correct 289 ms 10116 KB Output is correct
14 Correct 298 ms 10092 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 1444 KB Output is correct
2 Correct 43 ms 2520 KB Output is correct
3 Correct 65 ms 3620 KB Output is correct
4 Correct 194 ms 9988 KB Output is correct
5 Correct 199 ms 10000 KB Output is correct
6 Correct 188 ms 10112 KB Output is correct
7 Correct 192 ms 10068 KB Output is correct
8 Correct 188 ms 9992 KB Output is correct
9 Correct 192 ms 10120 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 488 KB Output is correct
2 Correct 22 ms 1388 KB Output is correct
3 Correct 202 ms 8572 KB Output is correct
4 Correct 255 ms 10708 KB Output is correct
5 Correct 246 ms 10704 KB Output is correct
6 Correct 251 ms 10716 KB Output is correct
7 Correct 249 ms 10712 KB Output is correct
8 Correct 251 ms 10700 KB Output is correct
9 Correct 251 ms 10712 KB Output is correct
10 Correct 254 ms 10740 KB Output is correct
11 Correct 271 ms 10140 KB Output is correct
12 Correct 269 ms 10136 KB Output is correct
13 Correct 285 ms 10112 KB Output is correct
14 Correct 317 ms 9988 KB Output is correct
15 Correct 227 ms 10736 KB Output is correct
16 Correct 256 ms 10748 KB Output is correct
17 Correct 288 ms 10136 KB Output is correct
18 Correct 269 ms 10124 KB Output is correct
19 Correct 267 ms 10720 KB Output is correct
20 Correct 282 ms 10120 KB Output is correct
21 Runtime error 147 ms 17596 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1436 KB Output is correct
2 Correct 45 ms 1552 KB Output is correct
3 Correct 275 ms 11204 KB Output is correct
4 Correct 307 ms 11708 KB Output is correct
5 Correct 364 ms 13020 KB Output is correct
6 Correct 383 ms 12752 KB Output is correct
7 Correct 370 ms 12860 KB Output is correct
8 Correct 358 ms 12808 KB Output is correct
9 Incorrect 244 ms 8792 KB Output is incorrect: {s, t} is wrong.
10 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 1400 KB Output is correct
2 Correct 38 ms 1684 KB Output is correct
3 Correct 332 ms 11084 KB Output is correct
4 Correct 282 ms 11292 KB Output is correct
5 Correct 300 ms 11584 KB Output is correct
6 Correct 372 ms 12836 KB Output is correct
7 Correct 285 ms 11260 KB Output is correct
8 Correct 298 ms 11404 KB Output is correct
9 Correct 312 ms 11680 KB Output is correct
10 Correct 372 ms 12884 KB Output is correct
11 Correct 388 ms 12804 KB Output is correct
12 Correct 349 ms 12752 KB Output is correct
13 Incorrect 276 ms 9932 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -