Submission #953359

#	Time	Username	Problem	Language	Result	Execution time	Memory
953359		waldi	Simurgh (IOI17_simurgh)	C++17	51 / 100	89 ms	4444 KiB

simurgh

#include "simurgh.h"
#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int((x).size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

vector<int> find_roads(int n, vector<int> poczatki, vector<int> konce){
	int m = ssize(poczatki);
	vector<vector<pii>> g(n);
	REP(i, m){
		int a = poczatki[i], b = konce[i];
		g[a].emplace_back(b, i);
		g[b].emplace_back(a, i);
	}
	
	vector<int> odpowiedz(m, -1);
	
	REP(wierz, n){
		vector<int> rozp;
		vector<int> bylo(n, 0), odw(n, 0);
		function<void(int)> dfs_raz = [&](int w){
			bylo[w] = odw[w] = 1;
			for(pii i : g[w]) if(i.fi!=wierz && !odw[i.fi]) rozp.emplace_back(i.se), dfs_raz(i.fi);
		};
		vector<int> odw2(n, 0);
		function<void(int)> dfs_dwa = [&](int w){
			odw2[w] = 1;
			for(pii i : g[w]) if(!odw2[i.fi]) rozp.emplace_back(i.se), dfs_dwa(i.fi);
		};
		REP(sas, n) if(sas != wierz && !bylo[sas]){
			rozp.clear();
			odw = vector<int>(n, 0);
			dfs_raz(sas);
			odw2 = odw;
			dfs_dwa(wierz);
			
			int maks = -1;
			for(pii i : g[wierz]) if(odw[i.fi] && odpowiedz[i.se] == 1){
				rozp.emplace_back(i.se);
				maks = count_common_roads(rozp);
				rozp.pop_back();
				break;
			}
			
			vector<pii> vec;
			for(pii i : g[wierz]) if(odw[i.fi] && odpowiedz[i.se] < 0){
				rozp.emplace_back(i.se);
				vec.emplace_back(i.se, count_common_roads(rozp));
				maks = max(maks, vec.back().se);
				rozp.pop_back();
			}
			for(pii i : vec) odpowiedz[i.fi] = i.se==maks;
		}
	}
	
	vector<int> ret;
	REP(i, m) if(odpowiedz[i] == 1) ret.emplace_back(i);
	return ret;
}

• Subtask 1: 13 / 13
• Subtask 2: 17 / 17
• Subtask 3: 21 / 21
• Subtask 4: 0 / 19
• Subtask 5: 0 / 30