oj.uz

Submission #793169

# Submission time Handle Problem Language Result Execution time Memory
793169 2023-07-25T14:51:53 Z welleyth Highway Tolls (IOI18_highway) C++17
51 / 100
 282 ms 16612 KB 
#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

constexpr int NN = 90000;

//#define int long long

typedef long long ll;

vector<pair<int,int>> g[NN];
vector<pair<int,int>> BFSTree[NN];
bool can[NN];
bool marked[NN];
bool wasL[NN],wasR[NN];
bool banned[NN];

void dfs(int v,int& c){
    marked[v] = true;
    c -= can[v];
    for(auto&[to,id] : g[v]){
        if(c > 0 && !marked[to]){
            dfs(to,c);
        }
    }
    return;
}

void dfsL(int v,int& c){
    if(wasL[v]){
        marked[v] = true;
        c -= can[v];
    }
//    cerr << "v: " << v << ", marked: " << marked[v] << "\n";
    for(auto&[to,id] : BFSTree[v]){
        if(c > 0 && !marked[to] && wasL[to]){
            dfsL(to,c);
        }
    }
    return;
}

void dfsR(int v,int& c){
    if(wasR[v]){
        marked[v] = true;
        c -= can[v];
    }
    for(auto&[to,id] : BFSTree[v]){
        if(c > 0 && !marked[to] && wasR[to]){
            dfsR(to,c);
        }
    }
    return;
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B){
    int m = U.size();

    for(int i = 0; i < m; i++){
        g[U[i]].push_back(make_pair(V[i],i));
        g[V[i]].push_back(make_pair(U[i],i));
    }

    vector<int> w(m,0);
    ll minVal = ask(w);

    for(int i = 0; i < N; i++){
        can[i] = true;
    }

    int edgeID = -1;

    {
        vector<int> v;
        for(int i = 0; i < m; i++) v.push_back(i);
        bool s[m];
        for(int i = 0; i < m; i++){
            s[i] = 0;
        }
        while(v.size() > 1){
            vector<int> L,R;
            for(auto& id : v){
                if(R.size() < L.size())
                    R.push_back(id);
                else
                    L.push_back(id);
            }
            for(int i = 0; i < m; i++) w[i] = s[i];
            for(auto& id : L) w[id] = 1;
            ll val1 = ask(w);
            if(val1 > minVal){

                v = L;
            }
            else {
                for(auto& id : L) s[id] = true;
                v = R;
            }
        }
        assert(!v.empty());
        edgeID = v[0];
    }
//    cerr << "edge: " << U[edgeID] << " " << V[edgeID] << "\n";

//    /// DEBUG: check that edgeID is not the path.
//    {
//        queue<int> q;
//        q.push(0);
//        bool used[N];
//        memset(used,0,sizeof used);
//        used[0] = true;
//        while(!q.empty()){
//            int v = q.front();
//            q.pop();
//            for(auto&[to,id] : g[v]){
//                if(edgeID == id) continue;
//                if(!used[to]){
//                    used[to] = true;
//                    q.push(to);
//                }
//            }
//        }
//        assert(!used[66138]);
//    }

    vector<int> BFSEdges;
    {
        bool used[N];
        memset(used,0,sizeof used);
        queue<int> q;
        q.push(U[edgeID]);
        used[U[edgeID]] = true;

        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(auto&[to,id] : g[v]){
                if(!used[to]){
                    used[to] = true;
                    q.push(to);
                    BFSEdges.push_back(id);
                    BFSTree[v].push_back(make_pair(to,id));
                    BFSTree[to].push_back(make_pair(v,id));
                }
            }
        }
    }

    {
        int u = U[edgeID], v = V[edgeID];
        banned[u] = banned[v] = true;
        queue<int> q;
        q.push(u);
        while(!q.empty()){
            int vv = q.front();
            wasL[vv] = true;
            can[vv] = true;
            q.pop();
            for(auto&[to,id] : BFSTree[vv]){
                if(!banned[to] && !wasL[to]){
                    wasL[to] = true;
                    can[to] = true;
                    q.push(to);
                }
            }
        }
        q.push(v);
        while(!q.empty()){
            int vv = q.front();
            q.pop();
            wasR[vv] = true;
            can[vv] = true;
            for(auto&[to,id] : BFSTree[vv]){
                if(!banned[to] && !wasR[to]){
                    wasR[to] = true;
                    can[to] = true;
                    q.push(to);
                }
            }
        }
    }

    bool notInBFSTRee[m];
    for(int i = 0; i < m; i++) notInBFSTRee[i] = true;
    for(auto& id : BFSEdges) notInBFSTRee[id] = false;

    int s,t;
    s = t = -1;

    {
        int root = U[edgeID];
//        cerr << "root: " << root << "\n";
        int cnt = 0;
        for(int i = 0; i < N; i++){
            if(wasL[i]){
                cnt += can[i];
            }
        }
        while(cnt > 1){
            for(int i = 0; i < N; i++) marked[i] = false;
            int c = cnt/2;
//            cerr << "c: " << c << "\n";
            dfsL(root,c);
            vector<int> S1,S2;
            for(int i = 0; i < m; i++) w[i] = notInBFSTRee[i];
//            cerr << "marked: ";
//            for(int i = 0; i < N; i++){
//                if(marked[i])
//                    cerr << i << " ";
//            }
//            cerr << "\n";
            for(int i = 0; i < N; i++){
                for(auto&[to,id] : g[i]){
                    if(marked[i] && !marked[to] && !banned[to])
                        w[id] = true;
                }
            }
//            for(int i = 0; i < m; i++) w[i] |= borderLine[i];
            if(ask(w) > minVal){
                for(int i = 0; i < N; i++){
                    if(wasL[i] && marked[i])
                        can[i] = false;
                }
            } else {
                for(int i = 0; i < N; i++){
                    if(wasL[i] && !marked[i])
                        can[i] = false;
                }
            }

            cnt = 0;
            for(int i = 0; i < N; i++){
                if(wasL[i])
                    cnt += can[i];
            }
        }
        for(int i = 0; i < N; i++){
            if(wasL[i] && can[i])
                s = i;
        }
//        cerr << "s: " << s << "\n";
//        for(int i = 0; i < N; i++){
//            if(wasR[i])
//                cnt += can[i];
//        }
    }
//    return;
    {
        int root = V[edgeID];
//        cerr << "root: " << root << "\n";
        int cnt = 0;
        for(int i = 0; i < N; i++){
            if(wasR[i])
                cnt += can[i];
        }
        while(cnt > 1){
            for(int i = 0; i < N; i++) marked[i] = false;
            int c = cnt/2;
//            cerr << "c: " << c << "\n";
            dfsR(root,c);
            for(int i = 0; i < m; i++) w[i] = notInBFSTRee[i];
//            cerr << "marked: ";
//            for(int i = 0; i < N; i++){
//                if(marked[i])
//                    cerr << i << " ";
//            }
//            cerr << "\n";
            for(int i = 0; i < N; i++){
                for(auto&[to,id] : g[i]){
                    if(marked[i] && !marked[to] && !banned[to])
                        w[id] = true;
                }
            }
//            for(int i = 0; i < m; i++) w[i] |= borderLine[i];
            if(ask(w) > minVal){
                for(int i = 0; i < N; i++){
                    if(wasR[i] && marked[i])
                        can[i] = false;
                }
            } else {
                for(int i = 0; i < N; i++){
                    if(wasR[i] && !marked[i])
                        can[i] = false;
                }
            }

            cnt = 0;
            for(int i = 0; i < N; i++){
                if(wasR[i])
                    cnt += can[i];
            }
        }
        for(int i = 0; i < N; i++){
            if(wasR[i] && can[i])
                t = i;
        }

    }
//    cerr << s << " " << t << "\n";
//
    answer(s,t);

    return;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4560 KB Output is correct
2 Correct 12 ms 5480 KB Output is correct
3 Correct 210 ms 13712 KB Output is correct
4 Correct 170 ms 13844 KB Output is correct
5 Correct 139 ms 13840 KB Output is correct
6 Correct 168 ms 13864 KB Output is correct
7 Correct 196 ms 13772 KB Output is correct
8 Correct 143 ms 13872 KB Output is correct
9 Correct 134 ms 13888 KB Output is correct
10 Correct 169 ms 13876 KB Output is correct
11 Correct 153 ms 13512 KB Output is correct
12 Correct 155 ms 13388 KB Output is correct
13 Correct 131 ms 13408 KB Output is correct
14 Correct 147 ms 13764 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 5564 KB Output is correct
2 Correct 24 ms 6716 KB Output is correct
3 Correct 35 ms 7752 KB Output is correct
4 Correct 84 ms 13748 KB Output is correct
5 Correct 110 ms 13928 KB Output is correct
6 Correct 86 ms 14836 KB Output is correct
7 Correct 106 ms 14708 KB Output is correct
8 Correct 120 ms 13988 KB Output is correct
9 Correct 98 ms 14232 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4560 KB Output is correct
2 Correct 13 ms 5480 KB Output is correct
3 Correct 127 ms 11844 KB Output is correct
4 Correct 119 ms 13836 KB Output is correct
5 Correct 138 ms 13860 KB Output is correct
6 Correct 144 ms 13792 KB Output is correct
7 Correct 129 ms 13812 KB Output is correct
8 Correct 167 ms 13776 KB Output is correct
9 Correct 154 ms 13872 KB Output is correct
10 Correct 132 ms 13888 KB Output is correct
11 Correct 178 ms 13404 KB Output is correct
12 Correct 161 ms 14112 KB Output is correct
13 Correct 177 ms 13736 KB Output is correct
14 Correct 166 ms 13840 KB Output is correct
15 Correct 117 ms 13792 KB Output is correct
16 Correct 155 ms 13880 KB Output is correct
17 Correct 174 ms 13604 KB Output is correct
18 Correct 111 ms 13824 KB Output is correct
19 Correct 104 ms 13732 KB Output is correct
20 Correct 100 ms 13748 KB Output is correct
21 Correct 124 ms 14552 KB Output is correct
22 Correct 110 ms 14448 KB Output is correct
23 Correct 147 ms 14356 KB Output is correct
24 Correct 178 ms 14448 KB Output is correct
25 Correct 223 ms 16612 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 5532 KB Output is correct
2 Correct 24 ms 5540 KB Output is correct
3 Correct 137 ms 14332 KB Output is correct
4 Correct 147 ms 14548 KB Output is correct
5 Correct 240 ms 15504 KB Output is correct
6 Correct 282 ms 15436 KB Output is correct
7 Correct 206 ms 15496 KB Output is correct
8 Correct 162 ms 15492 KB Output is correct
9 Correct 161 ms 11520 KB Output is correct
10 Correct 131 ms 11956 KB Output is correct
11 Incorrect 134 ms 12644 KB Output is incorrect: {s, t} is wrong.
12 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 5616 KB Output is correct
2 Correct 28 ms 5556 KB Output is correct
3 Correct 167 ms 14260 KB Output is correct
4 Correct 181 ms 14496 KB Output is correct
5 Correct 253 ms 14612 KB Output is correct
6 Correct 274 ms 15416 KB Output is correct
7 Correct 203 ms 14268 KB Output is correct
8 Correct 167 ms 14408 KB Output is correct
9 Correct 233 ms 14596 KB Output is correct
10 Correct 233 ms 15428 KB Output is correct
11 Correct 271 ms 15508 KB Output is correct
12 Correct 254 ms 15380 KB Output is correct
13 Incorrect 173 ms 12652 KB Output is incorrect: {s, t} is wrong.
14 Halted 0 ms 0 KB -