oj.uz

Submission #297746

# Submission time Handle Problem Language Result Execution time Memory
297746 2020-09-11T21:05:44 Z MoNsTeR_CuBe Highway Tolls (IOI18_highway) C++17
51 / 100
 216 ms 22208 KB 
#include "highway.h"
    #include <bits/stdc++.h>
    using namespace std;
    void dfs(int node, int parent, vector< int > &index, vector< vector< pair<int,int> > > &Graph, int &curr, int lastEdge, vector< int > &EdgeToNode){
     
    	for(auto a: Graph[node]){
    		if(a.first == parent) continue;
    		dfs(a.first, node, index, Graph, curr, a.second, EdgeToNode);
    	}	
    	index[curr++] = lastEdge;
    	if(lastEdge != -1) EdgeToNode[lastEdge] = node;
    }
     
    void search(int left, int right, int M, vector< int > &ans, vector< int > &EdgeToNode, vector< int > &index, long long mark){
      	if(left > right) return;
    	if(left == right){
    		ans.push_back(EdgeToNode[index[left]]);
    		return;
    	}
    	vector< int > toAsk(M,0);
    	int mid = (left+right)/2;
    	for(int i = 0; i<= mid; i++){
    		toAsk[index[i]] = 1;
    		//cout << EdgeToNode[index[i]] << ' ';
    	}
    	//cout << endl;
    	long long rep = ask(toAsk);
    	if(rep > mark){
    		search(left, mid, M, ans,EdgeToNode,index, mark);
    	}else{
    		search(mid+1, right, M, ans,EdgeToNode,index, mark);
    	}
    }
    void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
      int M = U.size();
      vector< vector< pair<int, int> > > Graph(N+10);
      for(int i = 0; i < M; i++){
    		Graph[U[i]].push_back({V[i],i});
    		Graph[V[i]].push_back({U[i],i});
      }
      
      int curr = 0;
      vector< int > index(N+10);
      vector< int > EdgeToNode(M+10);
      dfs(0, -1, index, Graph, curr,N, EdgeToNode);
      vector< int > ans;
      vector< int > toAsk(M);
      long long mark = ask(toAsk);
      search(0,M-1, M,ans,EdgeToNode,index, mark);
      //cout << ans[0] << endl;
      curr = 0;
      dfs(ans[0],-1,index,Graph,curr,N,EdgeToNode);
      //cout << "N" << endl;
      search(0,M-1, M,ans,EdgeToNode,index, mark);
      //cout << ans[1] << endl;
      assert((int)ans.size() == 2);
      answer(ans[0], ans[1]);
    }

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 1 ms 388 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 1 ms 256 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 380 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 288 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 15 ms 1792 KB Output is correct
3 Correct 161 ms 14236 KB Output is correct
4 Correct 173 ms 13884 KB Output is correct
5 Correct 162 ms 14388 KB Output is correct
6 Correct 167 ms 14224 KB Output is correct
7 Correct 175 ms 13916 KB Output is correct
8 Correct 156 ms 13920 KB Output is correct
9 Correct 197 ms 14076 KB Output is correct
10 Correct 165 ms 13928 KB Output is correct
11 Correct 168 ms 15752 KB Output is correct
12 Correct 183 ms 16992 KB Output is correct
13 Correct 171 ms 15988 KB Output is correct
14 Correct 171 ms 15788 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2680 KB Output is correct
2 Correct 25 ms 5064 KB Output is correct
3 Correct 43 ms 7416 KB Output is correct
4 Correct 136 ms 21764 KB Output is correct
5 Correct 128 ms 21948 KB Output is correct
6 Correct 121 ms 21876 KB Output is correct
7 Correct 121 ms 22120 KB Output is correct
8 Correct 134 ms 22208 KB Output is correct
9 Correct 134 ms 22196 KB Output is correct

Subtask #4
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 48 ms 1772 KB Output is correct
3 Correct 126 ms 10940 KB Output is correct
4 Correct 170 ms 14252 KB Output is correct
5 Correct 193 ms 14228 KB Output is correct
6 Correct 170 ms 13936 KB Output is correct
7 Correct 216 ms 14344 KB Output is correct
8 Correct 191 ms 14204 KB Output is correct
9 Correct 202 ms 14264 KB Output is correct
10 Correct 184 ms 14272 KB Output is correct
11 Correct 181 ms 15708 KB Output is correct
12 Correct 164 ms 17000 KB Output is correct
13 Correct 183 ms 16176 KB Output is correct
14 Correct 177 ms 16680 KB Output is correct
15 Correct 160 ms 14432 KB Output is correct
16 Correct 151 ms 14300 KB Output is correct
17 Correct 175 ms 16364 KB Output is correct
18 Correct 168 ms 16636 KB Output is correct
19 Correct 162 ms 14400 KB Output is correct
20 Correct 167 ms 17468 KB Output is correct
21 Correct 129 ms 14488 KB Output is correct
22 Correct 131 ms 14492 KB Output is correct
23 Correct 136 ms 14196 KB Output is correct
24 Correct 136 ms 14912 KB Output is correct
25 Correct 170 ms 20976 KB Output is correct

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 17368 KB Execution killed with signal 11 (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 32 ms 20352 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -