제출 #1361171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1361171		ddl	Type Printer (IOI08_printer)	C++20	90 / 100	111 ms	121252 KiB

printer

#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define all(v) (v).begin(), (v).end()
#define sz(v) (int)(v).size()
#define PI 3.14159265358979323846264
template<typename T>
using vec = vector<T>;
mt19937_64 rng(chrono::high_resolution_clock().now().time_since_epoch().count());
const int maxN = 25000;
const int alp = 27;
int n, ans, md[1000005];
string sl[maxN];
struct Trie{
	struct Node{
		int child[alp];
		int cnt;
		int end;
		Node() {
			cnt = end = 0;
			memset(child, -1, sizeof(child));
		}
	};
	vec<Node> trie;
	Trie() {
		trie.push_back(Node());
	}
	
	void add(const string& s) {
		int u = 0;
		//root of Trie
		for (auto& c : s) {
			int val = c - 'a';
			//if there's no child of u has symbol val -> add new node to trie
			//label as the size of current trie(+1 optional)
			if (trie[u].child[val] == -1) {
				trie[u].child[val] = sz(trie);
				trie.push_back(Node());
			}
			//move u to its child
			u = trie[u].child[val];
			trie[u].cnt++; 
		}
		trie[u].end++;
	}
};
string cur;
vec<char> ope;
//ope store the operation we will do
//this is a nice idea i havent thought about it
void init(int u, Trie& trie) {
	md[u] = 1;
	for (int i=0; i<26; ++i) {
		if (trie.trie[u].child[i] != -1) {
			int v = trie.trie[u].child[i];
			if (v == -1) continue;
			init(v, trie);
			md[u] = max(md[v] + 1, md[u]);
		}
	}
}
void dfs(Trie& trie, int u, bool order) {
	if (trie.trie[u].end) {
		ope.push_back('P');
	}
	int best = -1;
	int mx = 0;
	int fpt = -1;
	for (int i=0; i<26; ++i) {
		if (trie.trie[u].child[i] != -1) {
			int v = trie.trie[u].child[i];
			if (mx < md[v]) {
				mx = md[v];
				best = v;
				fpt = i;
			}
		}
	}
	for (int i=0; i<26; ++i) {
		if (trie.trie[u].child[i] == -1) continue;
		if (trie.trie[u].child[i] != best) {
			ope.push_back(i + 'a');
			dfs(trie, trie.trie[u].child[i], false);
			ope.push_back('-');
			//this is kinda like backtrack
		}
	}
	if (fpt != -1) {
		ope.push_back('a' + fpt);
		dfs(trie, best, order);
		if (!order) {
			ope.push_back('-');
		}
	}
}

void solve() {
	cin >> n;
	for (int i=1; i<=n; ++i) {
		cin >> sl[i];
	}
	Trie trie;
	for (int i=1; i<=n; ++i) {
		trie.add(sl[i]);
	}
	init(0, trie);
	dfs(trie, 0, true);
	//memory of trie of this problem is approximately 100MB which is ok
	//First: we solve the problem that we have to return 0(let the op clear)
	//so this is like
	//an euler tour in there
	
	//!!in this problem we see that per node only visit by 2 times or we operates
	//on it only 2 times one time is erase one time is add
	//!!so the total operations of all is 2 * (node(in trie) - 1)(for 0)
	
	//Second claim(real problem): in the end we do not need to erase
	//the one path to clear all the output currently
	//so the total is 2 * (node - 1) - (the one string called s) sz(s) + n
	//we will erase the longest one after
	
	//Third claim: the total solutions is
	//in dfs the current node of us is u 
	ans = 2 * (sz(trie.trie) - 1) + n;
	int u = 0;
	int mx = 0;
	for (int i=0; i<26; ++i) {
		if (trie.trie[u].child[i] != -1) {
			mx = max(mx, md[trie.trie[u].child[i]]);
		}
	}
	ans -= mx;
	cout << ans << "\n";
	for (char& c : ope) {
		cout << c << "\n";
	}
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    if(fopen("TASK.in", "r")){
        freopen("TASK.in", "r", stdin);
        freopen("TASK.out", "w", stdout);
    }
    int tc = 1;
    while (tc--) {
    	solve();
    }
    cerr << "\nTime elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << ".s\n";
}

컴파일 시 표준 에러 (stderr) 메시지

printer.cpp: In function 'int32_t main()':
printer.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen("TASK.in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
printer.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen("TASK.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 10 / 10
• 서브태스크 2: 10 / 10
• 서브태스크 3: 10 / 10
• 서브태스크 4: 10 / 10
• 서브태스크 5: 10 / 10
• 서브태스크 6: 10 / 10
• 서브태스크 7: 10 / 10
• 서브태스크 8: 10 / 10
• 서브태스크 9: 10 / 10
• 서브태스크 10: 0 / 10