oj.uz

Submission #1048391

# Submission time Handle Problem Language Result Execution time Memory
1048391 2024-08-08T07:15:58 Z pcc Simurgh (IOI17_simurgh) C++17
30 / 100
 3000 ms 11564 KB 
#include "simurgh.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 550;
pii par[mxn];
vector<pii> paths[mxn];
vector<pii> tree[mxn];
vector<int> back_edge;
int tp[mxn*mxn];
vector<pii> edges;
int dep[mxn];
vector<int> tree_edge;
set<int> tree_st;
int normal = 0;

/*
std::vector<int> r(n - 1);
for(int i = 0; i < n - 1; i++)
	r[i] = i;
int common = count_common_roads(r);
if(common == n - 1)
	return r;
r[0] = n - 1;
return r;
*/

void dfs(int now,int fa){
	for(auto &[nxt,id]:paths[now]){
		if(nxt == fa)continue;
		if(par[nxt].fs == -1){
			tree_edge.push_back(id);
			par[nxt] = pii(now,id);
			dep[nxt] = dep[now]+1;
			dfs(nxt,now);
		}
		else{
			back_edge.push_back(id);
		}
	}
	return;
}

int C = 0;

int ask(vector<int> &v){
	C++;
	assert(C<=30000);
	int re = count_common_roads(v);
	return re;
}

int ask(set<int> &st){
	vector<int> v;
	for(auto &i:st)v.push_back(i);
	return ask(v);
}

void solve_cycle(vector<int> &v,int eid){
	vector<int> res;
	auto st = tree_st;
	st.insert(eid);
	for(auto &i:v){
		st.erase(i);
		res.push_back(ask(st));
		st.insert(i);
	}
	st.erase(eid);
	int mn = *min_element(res.begin(),res.end());
	int mx = *max_element(res.begin(),res.end());
	cerr<<"CYCLE: "<<mx<<' '<<mn<<endl;for(auto &i:v)cerr<<i<<',';cerr<<endl;for(auto &i:res)cerr<<i<<',';cerr<<endl;
	if(mn == mx){
		if(normal == mn){
			tp[eid] = 0;
			for(auto &i:v)tp[i] = 0;
		}
		else if(normal<mn){
			tp[eid] = 1;
			for(auto &i:v)tp[i] = 0;
		}
		else if(normal>mn){
			tp[eid] = 0;
			for(auto &i:v)tp[i] = 1;
		}
	}
	else{
		assert(mx-mn == 1);
		if(mx>normal)tp[eid] = 1;
		else tp[eid] = 0;
		for(int i = 0;i<v.size();i++){
			if(res[i] == mx)tp[v[i]] = 0;
			else tp[v[i]] = 1;
		}
	}
	return;
}

void solve(int eid){
	auto [a,b] = edges[eid];
	if(dep[a]>dep[b])swap(a,b);
	int tmp = b;
	vector<int> v;
	while(tmp != a){
		v.push_back(par[tmp].sc);
		tmp = par[tmp].fs;
		//cerr<<v.back()<<','<<tmp<<' '<<a<<endl;
	}
	cerr<<"SOLVE: "<<eid<<"::";for(auto &i:v)cerr<<i<<',';cerr<<endl;
	int checker = -1;
	for(auto &i:v){
		if(tp[i] != -1)checker = i;
	}
	if(checker == -1)solve_cycle(v,eid);
	else{
		auto st = tree_st;
		st.erase(checker);
		st.insert(eid);
		int re = ask(st);
		if(re == normal)tp[eid] = tp[checker];
		else tp[eid] = tp[checker]^1;
		st.erase(eid);
		st.insert(checker);
		cerr<<"CHECKER: "<<checker<<','<<re<<endl;
		for(auto &i:v){
			if(tp[i] == -1){
				st.erase(i);
				st.insert(eid);
				cerr<<i<<"::";for(auto &j:st)cerr<<j<<',';cerr<<ask(st)<<endl;
				if(ask(st) == normal)tp[i] = tp[eid];
				else tp[i] = tp[eid]^1;
				st.insert(i);
				st.erase(eid);
			}
		}
	}
	cerr<<"EDGES: ";for(int i = 0;i<edges.size();i++)cerr<<tp[i]<<' ';cerr<<endl;
	return;
}

std::vector<int> find_roads(int n, std::vector<int> u, std::vector<int> v) {
	memset(tp,-1,sizeof(tp));
	for(auto &i:par)i = pii(-1,-1);
	for(int i = 0;i<u.size();i++){
		int a = u[i],b = v[i];
		edges.push_back(pii(a,b));
		paths[a].push_back(pii(b,i));
		paths[b].push_back(pii(a,i));
	}
	par[0] = pii(0,-1);
	dfs(0,0);
	sort(back_edge.begin(),back_edge.end());
	back_edge.resize(unique(back_edge.begin(),back_edge.end())-back_edge.begin());
	for(auto &i:tree_edge)tree_st.insert(i);
	cerr<<"TREE :";for(auto &i:tree_edge)cerr<<i<<',';cerr<<endl;
	normal = ask(tree_edge);
	cerr<<"NORMAL: "<<normal<<endl;
	for(auto &i:back_edge)solve(i);
	vector<int> ans;
	for(int i = 0;i<edges.size();i++)if(tp[i] != 0)ans.push_back(i);
	cerr<<C<<" ASKS"<<endl;
	cerr<<"ANS: ";for(auto &i:ans)cerr<<i<<',';cerr<<endl;
	return ans;
}

Compilation message

simurgh.cpp: In function 'void solve_cycle(std::vector<int>&, int)':
simurgh.cpp:94:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for(int i = 0;i<v.size();i++){
      |                 ~^~~~~~~~~
simurgh.cpp: In function 'void solve(int)':
simurgh.cpp:140:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  140 |  cerr<<"EDGES: ";for(int i = 0;i<edges.size();i++)cerr<<tp[i]<<' ';cerr<<endl;
      |                                ~^~~~~~~~~~~~~
simurgh.cpp: In function 'std::vector<int> find_roads(int, std::vector<int>, std::vector<int>)':
simurgh.cpp:147:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |  for(int i = 0;i<u.size();i++){
      |                ~^~~~~~~~~
simurgh.cpp:163:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  163 |  for(int i = 0;i<edges.size();i++)if(tp[i] != 0)ans.push_back(i);
      |                ~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB correct
2 Correct 1 ms 1624 KB correct
3 Correct 1 ms 1628 KB correct
4 Correct 1 ms 1496 KB correct
5 Correct 1 ms 1628 KB correct
6 Correct 1 ms 1628 KB correct
7 Correct 0 ms 1628 KB correct
8 Correct 1 ms 1628 KB correct
9 Correct 1 ms 1628 KB correct
10 Correct 1 ms 1628 KB correct
11 Correct 0 ms 1628 KB correct
12 Correct 1 ms 1628 KB correct
13 Correct 1 ms 1656 KB correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB correct
2 Correct 1 ms 1624 KB correct
3 Correct 1 ms 1628 KB correct
4 Correct 1 ms 1496 KB correct
5 Correct 1 ms 1628 KB correct
6 Correct 1 ms 1628 KB correct
7 Correct 0 ms 1628 KB correct
8 Correct 1 ms 1628 KB correct
9 Correct 1 ms 1628 KB correct
10 Correct 1 ms 1628 KB correct
11 Correct 0 ms 1628 KB correct
12 Correct 1 ms 1628 KB correct
13 Correct 1 ms 1656 KB correct
14 Correct 2419 ms 5216 KB correct
15 Correct 2542 ms 5232 KB correct
16 Correct 2491 ms 5204 KB correct
17 Correct 1611 ms 4100 KB correct
18 Correct 210 ms 1972 KB correct
19 Correct 1747 ms 4296 KB correct
20 Correct 1534 ms 3920 KB correct
21 Correct 1387 ms 3540 KB correct
22 Correct 765 ms 2780 KB correct
23 Correct 612 ms 2388 KB correct
24 Correct 564 ms 2532 KB correct
25 Correct 7 ms 1624 KB correct
26 Correct 603 ms 2320 KB correct
27 Correct 613 ms 2384 KB correct
28 Correct 102 ms 1700 KB correct
29 Correct 22 ms 1628 KB correct
30 Correct 590 ms 2384 KB correct
31 Correct 662 ms 2392 KB correct
32 Correct 608 ms 2644 KB correct
33 Correct 607 ms 2644 KB correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB correct
2 Correct 1 ms 1624 KB correct
3 Correct 1 ms 1628 KB correct
4 Correct 1 ms 1496 KB correct
5 Correct 1 ms 1628 KB correct
6 Correct 1 ms 1628 KB correct
7 Correct 0 ms 1628 KB correct
8 Correct 1 ms 1628 KB correct
9 Correct 1 ms 1628 KB correct
10 Correct 1 ms 1628 KB correct
11 Correct 0 ms 1628 KB correct
12 Correct 1 ms 1628 KB correct
13 Correct 1 ms 1656 KB correct
14 Correct 2419 ms 5216 KB correct
15 Correct 2542 ms 5232 KB correct
16 Correct 2491 ms 5204 KB correct
17 Correct 1611 ms 4100 KB correct
18 Correct 210 ms 1972 KB correct
19 Correct 1747 ms 4296 KB correct
20 Correct 1534 ms 3920 KB correct
21 Correct 1387 ms 3540 KB correct
22 Correct 765 ms 2780 KB correct
23 Correct 612 ms 2388 KB correct
24 Correct 564 ms 2532 KB correct
25 Correct 7 ms 1624 KB correct
26 Correct 603 ms 2320 KB correct
27 Correct 613 ms 2384 KB correct
28 Correct 102 ms 1700 KB correct
29 Correct 22 ms 1628 KB correct
30 Correct 590 ms 2384 KB correct
31 Correct 662 ms 2392 KB correct
32 Correct 608 ms 2644 KB correct
33 Correct 607 ms 2644 KB correct
34 Execution timed out 3051 ms 8784 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB correct
2 Correct 4 ms 1628 KB correct
3 Execution timed out 3094 ms 11564 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1624 KB correct
2 Correct 1 ms 1624 KB correct
3 Correct 1 ms 1628 KB correct
4 Correct 1 ms 1496 KB correct
5 Correct 1 ms 1628 KB correct
6 Correct 1 ms 1628 KB correct
7 Correct 0 ms 1628 KB correct
8 Correct 1 ms 1628 KB correct
9 Correct 1 ms 1628 KB correct
10 Correct 1 ms 1628 KB correct
11 Correct 0 ms 1628 KB correct
12 Correct 1 ms 1628 KB correct
13 Correct 1 ms 1656 KB correct
14 Correct 2419 ms 5216 KB correct
15 Correct 2542 ms 5232 KB correct
16 Correct 2491 ms 5204 KB correct
17 Correct 1611 ms 4100 KB correct
18 Correct 210 ms 1972 KB correct
19 Correct 1747 ms 4296 KB correct
20 Correct 1534 ms 3920 KB correct
21 Correct 1387 ms 3540 KB correct
22 Correct 765 ms 2780 KB correct
23 Correct 612 ms 2388 KB correct
24 Correct 564 ms 2532 KB correct
25 Correct 7 ms 1624 KB correct
26 Correct 603 ms 2320 KB correct
27 Correct 613 ms 2384 KB correct
28 Correct 102 ms 1700 KB correct
29 Correct 22 ms 1628 KB correct
30 Correct 590 ms 2384 KB correct
31 Correct 662 ms 2392 KB correct
32 Correct 608 ms 2644 KB correct
33 Correct 607 ms 2644 KB correct
34 Execution timed out 3051 ms 8784 KB Time limit exceeded
35 Halted 0 ms 0 KB -