oj.uz

Submission #953347

# Submission time Handle Problem Language Result Execution time Memory
953347 2024-03-25T20:47:19 Z waldi Simurgh (IOI17_simurgh) C++17
0 / 100
 1 ms 344 KB 
#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);
		};
		function<void(int)> dfs_dwa = [&](int w){
			odw[w] = 1;
			for(pii i : g[w]) if(!odw[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);
			dfs_dwa(wierz);
			
			int maks = -1;
			for(pii i : g[wierz]) if(odw[i.fi] && odpowiedz[i.fi] == 1){
				rozp.emplace_back(i.fi);
				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
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB WA in grader: NO
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB correct
2 Incorrect 0 ms 344 KB WA in grader: NO
3 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB WA in grader: NO
2 Halted 0 ms 0 KB -