oj.uz

Submission #108799

# Submission time Handle Problem Language Result Execution time Memory
108799 2019-05-02T07:21:41 Z tri Highway Tolls (IOI18_highway) C++14
13 / 100
 372 ms 17632 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;

void 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 == 0) {
        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 < M; 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 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 324 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Runtime error 2 ms 424 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 400 KB Output is correct
2 Correct 29 ms 1412 KB Output is correct
3 Correct 257 ms 10720 KB Output is correct
4 Correct 253 ms 10704 KB Output is correct
5 Correct 266 ms 10736 KB Output is correct
6 Correct 253 ms 10728 KB Output is correct
7 Correct 237 ms 10660 KB Output is correct
8 Correct 240 ms 10720 KB Output is correct
9 Correct 247 ms 10732 KB Output is correct
10 Correct 295 ms 10728 KB Output is correct
11 Correct 284 ms 10120 KB Output is correct
12 Correct 284 ms 10136 KB Output is correct
13 Correct 262 ms 10136 KB Output is correct
14 Correct 292 ms 10136 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 1460 KB Output is correct
2 Correct 56 ms 2552 KB Output is correct
3 Correct 54 ms 3632 KB Output is correct
4 Correct 211 ms 9992 KB Output is correct
5 Correct 208 ms 10048 KB Output is correct
6 Correct 172 ms 10300 KB Output is correct
7 Correct 208 ms 10068 KB Output is correct
8 Correct 177 ms 9984 KB Output is correct
9 Correct 196 ms 10116 KB Output is correct

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 28 ms 1484 KB Output is correct
3 Correct 184 ms 8584 KB Output is correct
4 Correct 259 ms 10768 KB Output is correct
5 Correct 243 ms 10716 KB Output is correct
6 Correct 245 ms 10648 KB Output is correct
7 Correct 245 ms 10656 KB Output is correct
8 Correct 249 ms 10696 KB Output is correct
9 Correct 279 ms 10728 KB Output is correct
10 Correct 269 ms 10724 KB Output is correct
11 Correct 316 ms 10132 KB Output is correct
12 Correct 277 ms 10128 KB Output is correct
13 Correct 283 ms 10092 KB Output is correct
14 Correct 260 ms 9996 KB Output is correct
15 Correct 238 ms 10728 KB Output is correct
16 Correct 230 ms 10728 KB Output is correct
17 Correct 286 ms 10068 KB Output is correct
18 Correct 312 ms 10076 KB Output is correct
19 Correct 229 ms 10712 KB Output is correct
20 Correct 259 ms 10116 KB Output is correct
21 Runtime error 173 ms 17632 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 27 ms 1424 KB Output is correct
2 Correct 27 ms 1704 KB Output is correct
3 Correct 295 ms 11200 KB Output is correct
4 Correct 304 ms 11700 KB Output is correct
5 Correct 372 ms 13088 KB Output is correct
6 Correct 354 ms 12840 KB Output is correct
7 Correct 371 ms 12848 KB Output is correct
8 Correct 370 ms 12816 KB Output is correct
9 Incorrect 258 ms 8852 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 28 ms 1536 KB Output is correct
2 Correct 29 ms 1676 KB Output is correct
3 Correct 295 ms 11176 KB Output is correct
4 Correct 306 ms 11356 KB Output is correct
5 Correct 302 ms 11616 KB Output is correct
6 Correct 347 ms 12760 KB Output is correct
7 Correct 253 ms 11256 KB Output is correct
8 Correct 293 ms 11404 KB Output is correct
9 Correct 316 ms 11600 KB Output is correct
10 Correct 368 ms 12800 KB Output is correct
11 Correct 371 ms 12880 KB Output is correct
12 Correct 347 ms 12748 KB Output is correct
13 Correct 232 ms 9956 KB Output is correct
14 Incorrect 223 ms 9060 KB Output is incorrect: {s, t} is wrong.
15 Halted 0 ms 0 KB -