oj.uz

Submission #136484

# Submission time Handle Problem Language Result Execution time Memory
136484 2019-07-25T11:08:21 Z Nucleist Highway Tolls (IOI18_highway) C++14
5 / 100
 424 ms 24712 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; }
};
int dist[90001];
vector<int>adj[90001];
bool vis[90001];
map<pair<int,int>,int>gg;
map<pair<int,int>,int>gg1;
map<int,vector<int>>gg2;
int s,t;
int 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()-1;
	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];
        }
        int 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 2428 KB Output is correct
4 Correct 4 ms 2424 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 2344 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 2424 KB Output is correct
12 Correct 4 ms 2428 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2552 KB Output is correct
2 Correct 53 ms 4308 KB Output is correct
3 Correct 401 ms 19284 KB Output is correct
4 Correct 398 ms 19288 KB Output is correct
5 Correct 383 ms 19280 KB Output is correct
6 Correct 388 ms 19268 KB Output is correct
7 Correct 384 ms 19276 KB Output is correct
8 Correct 372 ms 19288 KB Output is correct
9 Correct 405 ms 19372 KB Output is correct
10 Correct 388 ms 19288 KB Output is correct
11 Correct 407 ms 23128 KB Output is correct
12 Correct 411 ms 24712 KB Output is correct
13 Correct 413 ms 23520 KB Output is correct
14 Incorrect 424 ms 22176 KB Output is incorrect: {s, t} is wrong.

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 6096 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 2604 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 26 ms 4696 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 35 ms 4600 KB Output is incorrect: {s, t} is wrong.
2 Halted 0 ms 0 KB -