oj.uz

Submission #430476

# Submission time Handle Problem Language Result Execution time Memory
430476 2021-06-16T14:24:50 Z Mohammed_Atalah Duathlon (APIO18_duathlon) C++17
0 / 100
 1000 ms 1048580 KB 
/////home/mohammed/.config/sublime-text-3/Packages/User

/*input

*/
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <math.h>
#include <sstream>
#include <iterator>
#include <cstdlib>
#include <unordered_map>
#include <map>
#include <list>
#include <set>

using namespace std;
using bin = std::bitset<8>;

#define endl ("\n")
#define pi (3.141592653589)
#define mod 1000000007
#define int int64_t
#define float double
#define ll long long
#define pb push_back
// #define mp make_pair
#define ff first
#define ss second
#define all(c) c.begin(), c.end()
#define min3(a, b, c) min({a,b,c})
#define max3(a, b, c) max({a,b,c})
#define min4(a, b, c, d) min({a,b,c,d})
#define max4(a, b, c, d) max({a,b,c,d})
#define rrep(i, n) for(int i=n-1;i>=0;i--)
#define rep(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ld long double
#define scanArray(a,n) for(int i = 0; i < n; i++){cin >> a[i];}
#define coutArray(a,n) for(int i = 0; i < n; i++){cout << a[i] << " ";};cout << endl;
#define input(type, n) type n; cin>>n;



struct debugger
{
	template<typename T> debugger& operator , (const T& v)
	{
		cerr << v << " ";
		return *this;
	}
} dbg;

bool check_key(map<int, int> m, int key)
{
	if (m.find(key) == m.end())
		return false;

	return true;
}


vector<int> SieveOfEratosthenes(int n)
{
	bool prime[n + 1];
	memset(prime, true, sizeof(prime));


	vector<int> res;
	for (int p = 2; p * p <= n; p++)
	{
		if (prime[p] == true)
		{
			for (int i = p * p; i <= n; i += p)
				prime[i] = false;
		}
	}

	for (int p = 2; p <= n; p++)
		if (prime[p])
			res.push_back(p);
	//cout << p << " ";
	return res;
}

// function to convert decimal to binary
bin decToBinary(int n)
{
	// array to store binary number
	int binaryNum[32];

	// counter for binary array
	int i = 0;
	while (n > 0) {

		// storing remainder in binary array
		binaryNum[i] = n % 2;
		n = n / 2;
		i++;
	}
	string x = "";
	// printing binary array in reverse order
	for (int j = i - 1; j >= 0; j--) {
		x += to_string(binaryNum[j]);
	}
	bin result{x};
	return result;
}
// for example:
// bin result = decToBinary(2);
// bin result2 = decToBinary(10);
// bin z = result xor result2;
// cout << z;
// return 0;
int convertBinaryToDecimal(long long n)
{
	int decimalNumber = 0, i = 0, remainder;
	while (n != 0)
	{
		remainder = n % 10;
		n /= 10;
		decimalNumber += remainder * pow(2, i);
		++i;
	}
	return decimalNumber;
}
int factorial(int n) {

	long long res = 1;
	for (int i = 1; i <= n; i++) {
		res = ((res * i) % mod + mod) % mod ;
	}
	return res;
}



vector<int> vis;
vector<set<int>> edg;
set<vector<int>> res;
map<string, int> mp;
map<string, set<int>> mq;
// int res = 0;


void solve(int num, vector<int> con, int times, string masar) {

	if (con.size() == 3) {
		res.insert(con);
		// coutArray(con , 3);
		return;
	}




	for (auto e : edg[num]) {
		// if (con.size() == 2 && con[0] == 1 && con[1] == 4) {
		// 	cout << vis[e] << endl;
		// }
		if (vis[e] != 1) {
			con.pb(e);
			vis[e] = 1;
			string s = "";
			for (auto r : con) {
				s += char(r + 48);
			}

			if ( s.size() == 3) {
				// cout << endl;
				// cout << masar << endl;
				// cout << s << endl;
				mp[s]++;
				s.pop_back();
				// cout << s << endl;
				mq[s].insert(e);
				solve(e, con, times + 1, masar + to_string(e));
			} else if (s.size() != 3 && mq[s].size() < vis.size() - 3) {
				// cout << s << " " << e << endl;
				solve(e, con, times + 1, masar + to_string(e));
			}

			con.pop_back();
			// s.pop_back();
			// if (mq[s][e] == 0) {
			// mq[s][e] = 1;
			// cout << s << " " << e << endl;

			solve(e, con, times + 1, masar + to_string(e));

			// }
			vis[e] = 0;
		}
	}

}



int32_t main()
{
	fast;
// #ifndef ONLINE_JUDGE
// 	freopen("input.txt", "r", stdin);
// 	freopen("output.txt", "w", stdout);
// #endif

	input(int, inter); input(int, roads);
	vis.resize(inter + 1);
	edg.resize(inter + 1);


	while (roads--) {
		input(int, num1); input(int, num2);
		edg[num1].insert(num2);
		edg[num2].insert(num1);
	}

	for (int i = 1; i < inter + 1; i++) {
		vector<int> v;
		v.pb(i);
		vis[i] = 1;
		solve(i, v, 1, to_string(i));
		v.pop_back();
		// solve(i, v, 1);
		vis[i] = 0;
	}
	cout << res.size() << endl;

	// for (auto e : edg[2]) {
	// 	cout << e << endl;
	// }



}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 22 ms 332 KB Output is correct
9 Correct 300 ms 444 KB Output is correct
10 Execution timed out 1092 ms 312 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 22 ms 332 KB Output is correct
9 Correct 300 ms 444 KB Output is correct
10 Execution timed out 1092 ms 312 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 875 ms 1048580 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 123408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1098 ms 79660 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1087 ms 131736 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1093 ms 80896 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 22 ms 332 KB Output is correct
9 Correct 300 ms 444 KB Output is correct
10 Execution timed out 1092 ms 312 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 22 ms 332 KB Output is correct
9 Correct 300 ms 444 KB Output is correct
10 Execution timed out 1092 ms 312 KB Time limit exceeded
11 Halted 0 ms 0 KB -