oj.uz

Submission #139411

# Submission time Handle Problem Language Result Execution time Memory
139411 2019-07-31T16:18:04 Z wilwxk Highway Tolls (IOI18_highway) C++14
12 / 100
 566 ms 262148 KB 
#include "highway.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN=9e4+5;
vector<int> g[MAXN], config;
vector<int> bons;
int aresta[MAXN*2][2];
int pid[MAXN], lvl[MAXN];
bool ruim[MAXN];
int n, m, x, y;
ll tam;

void pinta(int ini, int fim, int k) {
  if(fim<ini||ini<0) return;
  for(int i=ini; i<=fim; i++) config[pid[bons[i]]]=k;
}

void dfs(int cur, int pp, int d) {
	pid[cur]=pp; lvl[cur]=d;
	for(auto vid : g[cur]) {
		if(vid==pp) continue;
		int viz= aresta[vid][ aresta[vid][0]==cur ];
		dfs(viz, vid, d+1);
	}
}

// int divide(int cur) {
// 	return 1;
//   for(auto vid : g[cur]) {
		
// 	}
// }

// int conquer(int cur) {

// }

void acaba() {
  if(bons.size()==1) {
    answer(bons[0], 0);
    return;
  }
  // for(auto cur : bons) printf("bb %d (%d)\n", cur, pid[cur]); cout << endl;
  
  vector<int> aux;
  int mid=(bons.size()-1)/2;
  pinta(0, mid, 1);
  ll val=ask(config);
  // for(auto cur : config) printf("%d ", cur); printf(">> %d %lld %lld\n", mid, val, tam);

  if(val==tam) {
    for(int i=mid+1; i<bons.size(); i++) aux.push_back(bons[i]);
    bons.clear();
    for(auto cur : aux) bons.push_back(cur);
  }
  else if(val==tam+(y-x)) {
    for(int i=0; i<=mid; i++) aux.push_back(bons[i]);
    bons.clear();
    for(auto cur : aux) bons.push_back(cur);
  }
  else {
    pinta(0, mid, 0);
    random_shuffle(bons.begin(), bons.end());
  }
  pinta(0, mid, 0);

  acaba();
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
  n=N; m=U.size(); x=A; y=B;
  for(int i=0; i<m; i++) {
  	int a=U[i]; int b=V[i];
  	aresta[i][0]=a; aresta[i][1]=b;
  	g[a].push_back(i);
  	g[b].push_back(i);
  	config.push_back(0);
  }

  dfs(0, -1, 0);
  tam=ask(config);
  for(int i=1; i<n; i++) {
    if(lvl[i]==tam/x) bons.push_back(i);
    else ruim[i]=1;
  }

  // for(int i=0; i<n; i++) {
  //   if(ruim[i]) {
  //     dfs(i, -1, 0);
  //     break;
  //   }
  // } 
  // bons.push_back(0);
  fill(config.begin(), config.end(), 0);
  srand(time(0)+n+m); random_shuffle(bons.begin(), bons.end());
  acaba();
}

Compilation message

highway.cpp: In function 'void acaba()':
highway.cpp:54:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=mid+1; i<bons.size(); i++) aux.push_back(bons[i]);
                      ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2424 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 2344 KB Output is correct
5 Correct 4 ms 2344 KB Output is correct
6 Correct 4 ms 2424 KB Output is correct
7 Correct 4 ms 2424 KB Output is correct
8 Correct 3 ms 2424 KB Output is correct
9 Correct 4 ms 2424 KB Output is correct
10 Correct 4 ms 2384 KB Output is correct
11 Correct 4 ms 2424 KB Output is correct
12 Correct 3 ms 2424 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2512 KB Output is correct
2 Correct 22 ms 3124 KB Output is correct
3 Correct 144 ms 8744 KB Output is correct
4 Correct 174 ms 8740 KB Output is correct
5 Correct 178 ms 8792 KB Output is correct
6 Correct 157 ms 8752 KB Output is correct
7 Correct 188 ms 8696 KB Output is correct
8 Correct 136 ms 8744 KB Output is correct
9 Correct 177 ms 8640 KB Output is correct
10 Correct 187 ms 8728 KB Output is correct
11 Correct 183 ms 9532 KB Output is correct
12 Correct 195 ms 9916 KB Output is correct
13 Correct 178 ms 9540 KB Output is correct
14 Correct 160 ms 9148 KB Output is correct

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 3532 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 4 ms 2512 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 Runtime error 566 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 485 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -