oj.uz

Submission #136493

# Submission time Handle Problem Language Result Execution time Memory
136493 2019-07-25T11:16:45 Z Nucleist Highway Tolls (IOI18_highway) C++14
12 / 100
 447 ms 25048 KB 
#include "highway.h"
#include <bits/stdc++.h> 
using namespace std; 
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define pb push_back
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
ll dist[90001];
vector<int>adj[90001];
bool vis[90001];
map<pair<int,int>,int>gg;
map<pair<int,int>,int>gg1;
map<ll,vector<int>>gg2;
ll s,t;
ll s1;
int n,m;
void dfs_tree(int node)
{
	dist[node]=s1;
	gg2[s1].pb(node);
	s1+=s;
	vis[node]=1;
	for (int i = 0; i < adj[node].size(); ++i)
	{
		if(vis[adj[node][i]]!=1)
			{	gg[{adj[node][i],node}]=gg1[{min(adj[node][i],node),max(adj[node][i],node)}];
				dfs_tree(adj[node][i]);}
	}
	s1-=s;
}
void find_pair(int N,vector<int>U, vector<int>V, int A, int B)
{
  //flash;
	n=N;
	m=U.size();
	for (int i = 0; i < m; ++i)
	{
		int x,y;
		x=U[i];
		y=V[i];
		adj[x].pb(y);
		adj[y].pb(x);
		gg1[{min(x,y),max(x,y)}]=i;
	}
	s=A;
	t=B;
	s1=0;
	dfs_tree(0);
	vector<int> now(m,0);
	ll vol = ask(now);
	int l = 0;
	vector<int> hioi = gg2[vol];
	int r = hioi.size();
	while (l <= r) {
		fill(now.begin(), now.end(), 0);
        int m = (l+r)/2;
        int last=0;
        for (int i = l; i <= m; ++i)
        {
        	auto voli = gg.lower_bound({hioi[i],-INF});
			auto kal = *voli;
			int kal1 = kal.second;
			now[kal1]=1;
			last=hioi[i];
        }
        ll dol = ask(now);
        if(l==r)
        {
        	answer(0,last);
        	return;
        }
        if(dol!=vol)r=m;
        else l=m+1;
    }
}
//code the AC sol !
// BS/queue/map

Compilation message

highway.cpp: In function 'void dfs_tree(int)':
highway.cpp:32:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < adj[node].size(); ++i)
                  ~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2344 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 4 ms 2424 KB Output is correct
4 Correct 4 ms 2428 KB Output is correct
5 Correct 4 ms 2424 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 4 ms 2424 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2424 KB Output is correct
11 Correct 4 ms 2552 KB Output is correct
12 Correct 4 ms 2424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 39 ms 4308 KB Output is correct
3 Correct 394 ms 19640 KB Output is correct
4 Correct 405 ms 19592 KB Output is correct
5 Correct 386 ms 19636 KB Output is correct
6 Correct 382 ms 19756 KB Output is correct
7 Correct 398 ms 19620 KB Output is correct
8 Correct 393 ms 19640 KB Output is correct
9 Correct 373 ms 19604 KB Output is correct
10 Correct 374 ms 19648 KB Output is correct
11 Correct 398 ms 23560 KB Output is correct
12 Correct 419 ms 25048 KB Output is correct
13 Correct 432 ms 23884 KB Output is correct
14 Correct 447 ms 22532 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 32 ms 6052 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 2612 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 4776 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 4724 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -