Submission #158155

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
158155	2019-10-15T06:06:28 Z	kig9981	Highway Tolls (IOI18_highway)	C++17	11 / 100	247 ms	15792 KB

highway

#include "highway.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> adj[90000];
set<int> gv[90000];
int g[90000];

void find_pair(int N, vector<int> U, vector<int> V, int A, int B)
{
	int M=U.size(), sg=0, tg=0, gnum=0;
	vector<int> W(M);
	long long dist=ask(W);
	queue<int> Q;
	for(int i=0;i<M;i++) {
		adj[U[i]].push_back(V[i]);
		adj[V[i]].push_back(U[i]);
	}
	for(int i=0;i<N;i++) gv[0].insert(i);
	while(gv[sg].size()>1) {
		int c=*gv[sg].begin();
		Q.push(c);
		g[c]=++gnum;
		gv[sg].erase(c);
		gv[gnum].insert(c);
		while(!Q.empty()) {
			c=Q.front();
			Q.pop();
			for(auto n: adj[c]) if(gv[gnum].size()<gv[sg].size() && g[n]==sg) {
				g[n]=gnum;
				gv[sg].erase(n);
				gv[gnum].insert(n);
				Q.push(n);
			}
		}
		if(gv[gnum].size()==1) {
			for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum || g[V[i]]==gnum;
			if(ask(W)==dist+B-A) sg=gnum;
		}
		else {
			for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum;
			if(sg==tg) {
				if(ask(W)>dist) sg=gnum;
				else {
					for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]==gnum;
					if(ask(W)>dist) sg=tg=gnum;
				}
			}
			else if(ask(W)==dist+B-A) sg=gnum;
		}
	}
	while(gv[tg].size()>1) {
		int c=*gv[tg].begin();
		Q.push(c);
		g[c]=++gnum;
		gv[tg].erase(c);
		gv[gnum].insert(c);
		while(!Q.empty()) {
			c=Q.front();
			Q.pop();
			for(auto n: adj[c]) if(gv[gnum].size()<gv[tg].size() && g[n]==tg) {
				g[n]=gnum;
				gv[tg].erase(n);
				gv[gnum].insert(n);
				Q.push(n);
			}
		}
		if(gv[gnum].size()==1) {
			for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum || g[V[i]]==gnum;
			if(ask(W)==dist+B-A) tg=gnum;
		}
		else {
			for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum;
			if(ask(W)==dist+B-A) tg=gnum;
		}
	}
	answer(*gv[sg].begin(),*gv[tg].begin());
}

Compilation message

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:42:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum;
                              ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
highway.cpp:74:44: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
    for(int i=0;i<M;i++) W[i]=g[U[i]]==gnum && g[V[i]]!=gnum || g[U[i]]!=gnum && g[V[i]]==gnum;
                              ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	6652 KB	Output is correct
2	Correct	8 ms	6648 KB	Output is correct
3	Correct	10 ms	6648 KB	Output is correct
4	Correct	9 ms	6668 KB	Output is correct
5	Correct	8 ms	6648 KB	Output is correct
6	Correct	8 ms	6648 KB	Output is correct
7	Correct	8 ms	6648 KB	Output is correct
8	Correct	7 ms	6672 KB	Output is correct
9	Correct	8 ms	6652 KB	Output is correct
10	Correct	8 ms	6668 KB	Output is correct
11	Correct	7 ms	6748 KB	Output is correct
12	Correct	8 ms	6648 KB	Output is correct

Subtask #2
0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	12 ms	6776 KB	Output is incorrect: more than 100 calls to ask.
2	Halted	0 ms	0 KB	-

Subtask #3
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	20 ms	7708 KB	Output is correct
2	Correct	54 ms	8600 KB	Output is correct
3	Correct	78 ms	9704 KB	Output is correct
4	Correct	231 ms	15664 KB	Output is correct
5	Correct	247 ms	15672 KB	Output is correct
6	Correct	207 ms	15792 KB	Output is correct
7	Correct	220 ms	15720 KB	Output is correct
8	Correct	180 ms	15748 KB	Output is correct
9	Correct	221 ms	15760 KB	Output is correct