제출 #1197479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197479		tkm_algorithms	Highway Tolls (IOI18_highway)	C++20	90 / 100	100 ms	11904 KiB

highway

/**
*    In the name of Allah
*    We are nothing and you're everything
**/
#include <bits/stdc++.h>
#include "highway.h"
using namespace std;
using ll = long long;

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

const char nl = '\n';

vector<int> w;
const int NN = 9e4+5;

int btreea[NN], whoma[NN];
int btreeb[NN], whomb[NN];
int cnt = 0;

//int ask(vector<int> w1) {
	//cnt += 1;
	//int cost = 0;
	//for (int i = 0; i < sz(w1); ++i) {
		//if (w1[i] == 1) {
			//if (i == 29 || i == 90 || i == 94 || i == 59 || i == 96 || i == 69 || i == 83 || i == 20 || i == 8 || i == 92)cost += 3;
		//} else 
			//if (i == 29 || i == 90 || i == 94 || i == 59 || i == 96 || i == 69 || i == 83 || i == 20 || i == 8 || i == 92)cost += 1;
	//}
	//return cost;
//}

//void answer(int x, int y) {
	//cout << x << " " << y;
	//cout << nl << cnt << nl;
//}

pair<int, int> solve(int n, vector<int> u, vector<int> v, int a, int b) {
	int m = sz(u);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    function<int(int, int)> rand = [&](int l, int r) {
        return uniform_int_distribution<int>(l, r)(rng);
    };
    
    function<vector<int>(vector<int>)> isolate = [&](vector<int> st) {
		vector<int> c(n+1), fnd(m);
		for (auto i: st)
			c[i] = 1;
		for (int i = 0; i < m; ++i) {
			fnd[i] = (c[u[i]] == c[v[i]]);
		}
		
		return fnd;
	};
    
    vector<int> S, T;
    while (1) {
		vector<int> s1, t1;
		for (int i = 0; i < n; ++i) {
			if (rand(0, 1))s1.push_back(i);
			else t1.push_back(i);
		}
		
		if (ask(isolate(s1))%2 ==1) {
			S = s1, T = t1;
			break;
		}
	}
	
	while (sz(S) > 1) {
		int mid = sz(S)>>1;
		if (ask(isolate(vector<int>(S.begin(), S.begin()+mid)))%2 == 1)S = vector<int>(S.begin(), S.begin()+mid);
		else S = vector<int>(S.begin()+mid, S.end());
	}
	
	while (sz(T) > 1) {
		int mid = sz(T)>>1;
		if (ask(isolate(vector<int>(T.begin(), T.begin()+mid)))%2 == 1)T = vector<int>(T.begin(), T.begin()+mid);
		else T = vector<int>(T.begin()+mid, T.end());
	}
	
	return {S[0], T[0]};
}

void find_pair(int N, vector<int> u, vector<int> v, int a, int b) {
	if (a == 1 && b == 2) {
		pair<int, int> ans;
		ans = solve(N, u, v, a, b);
		answer(ans.first, ans.second);
		return;
	}
	int m = sz(u), n = N;
	vector<pair<int, int>> g[n+1];
	w.resize(m);
	for (int i = 0; i < m; ++i) {
		g[u[i]].push_back({v[i], i});
		g[v[i]].push_back({u[i], i});
	}
	
	ll cost = ask(w), len = cost/a;
	
	int l = 0, r = m+1;
	while (r-l>1) {
		int mid = l+r>>1;
		for (int i = 0; i < m; ++i) {
			w[i] = 0;
			if (i < mid)w[i] = 1;
		}
		ll d = ask(w);
		if (d != cost)r = mid;
		else l = mid;
	}
	
	r--;
	int bir = r;
	queue<pair<int, int>> q;
	vector<int> vis(n+1);
	q.push({u[r], u[r]});
	vis[u[r]] = 1;
	bool ok = true;
	//cout << u[r] << " " << v[r] << nl;
	
	vector<int> need(m);
	
	int t = 1;
	while (!q.empty()) {
		int ux = q.front().first, p = q.front().second;
		q.pop();
		for (auto i: g[ux]) {
			if (i.first == p)continue;
			if (vis[i.first] == 1) {
				need[i.second] = 1;
				continue;
			}
			btreea[t++] = i.second;
			whoma[t-1] = i.first;
			vis[i.first] = 1;
			q.push({i.first, ux});
		}
	}
	
	int start = -1, end = -1;
	int sza = t-1;
	l = 0, r = sza+2;
	while (r-l>1) {
		int mid = l+r>>1;
		w = need;
		for (int i = 1; i <= sza; ++i) {
			int x = btreea[i];
			if (i >= mid)w[x] = 1;
		}
		ll d = ask(w);
		if (d != cost) {
			l = mid;
			ok = false;
		}
		else r = mid;
	}
	start = whoma[l];
	
	for (int i = 0; i < n; ++i)vis[i] = 0;
	for (int i = 0; i < m; ++i)need[i] = 0;
	
	t = 1;
	q.push({start, start});
	while (!q.empty()) {
		int ux = q.front().first, p = q.front().second;
		q.pop();
		for (auto i: g[ux]) {
			if (i.first == p)continue;
			if (vis[i.first] == 1) {
				need[i.second] = 1;
				continue;
			}
			btreeb[t++] = i.second;
			whomb[t-1] = i.first;
			vis[i.first] = 1;
			q.push({i.first, ux});
		}
	}

	int szb = t-1;
	l = 0, r = szb+2;
	while (r-l>1) {
		int mid = l+r>>1;
		w = need;
		for (int i = 1; i <= szb; ++i) {
			int x = btreeb[i];
			if (i >= mid)w[x] = 1;
		}
		ll d = ask(w);
		if (d != cost) {
			l = mid;
			ok = false;
		}
		else r = mid;
	}
	
	end = whomb[l];
	answer(start, end);
}


//void solve() {
	//int n, m, s, t, a, b; cin >> n >> m >> s >> t >> a >> b;
	//vector<int> u(m), v(m);
	//for (int i = 0; i < m; ++i) {
		//cin >> u[i] >> v[i];
	//}
	
	//find_pair(n, u, v, 1, 3);
//}

//int32_t main() {
    //ios::sync_with_stdio(0);
    //cin.tie(0);
    //int t = 1;
    //for (int _ = 0; _ < t; ++_) {
        //solve();
    //}
    //return 0;
//}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 6 / 6
• Subtask 4: 33 / 33
• Subtask 5: 18 / 18
• Subtask 6: 21 / 31