QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#298025#4632. Card Sharkdefyers#Compile Error//C++174.7kb2024-01-05 16:04:232024-01-05 16:04:23

Judging History

你现在查看的是最新测评结果

  • [2024-01-05 16:04:23]
  • 评测
查看
  • [2024-01-05 16:04:23]
  • 提交

answer

SA: 6 lcp: 0
SA: 1 lcp: 1
SA: 3 lcp: 2
SA: 5 lcp: 0
SA: 0 lcp: 2
SA: 2 lcp: 3
SA: 4 lcp: 1
Node 12 >>>   L: 0 R: 0 mnlen: 3 mxlen: 6
Edge: 12 -> 2
Node 2 >>>   L: 3 R: 3 mnlen: 1 mxlen: 5
Edge: 12 -> 9
Node 9 >>>   L: 2 R: 2 mnlen: 1 mxlen: 6
Edge: 9 -> 3
Node 3 >>>   L: 4 R: 4 mnlen: 3 mxlen: 3
Edge: 9 -> 7
Node 7 >>>   L: 3 R: 3 mnlen: 3 mxlen: 6
Edge: 7 -> 4
Node 4 >>>   L: 5 R: 5 mnlen: 4 mxlen: 8
Edge: 7 -> 5
Node 5 >>>   L: 6 R: 6 mnlen: 2 mxlen: 6

    ~/De/cp/icpc/2022-byte-dance  cd "/Users/ethen/Desktop/cp/icpc/2022-byte-dance/" && g++ -g -std=c++17 -fs
anitize=address,undefined -fno-sanitize-recover -fstack-protector-all -O2 D.cpp -o D

    ~/De/cp/icpc/2022-byte-dance  ./D < D1.in                                               ✔  16:03:53  
SA: 6 lcp: 0
SA: 1 lcp: 1
SA: 3 lcp: 2
SA: 5 lcp: 0
SA: 0 lcp: 2
SA: 2 lcp: 3
SA: 4 lcp: 1
Node 12 >>>   L: 3 R: 6 mnlen: 0 mxlen: 0
Edge: 12 -> 2
Node 2 >>>   L: 3 R: 3 mnlen: 1 mxlen: 5
Edge: 12 -> 9
Node 9 >>>   L: 4 R: 6 mnlen: 1 mxlen: 2
Edge: 9 -> 3
Node 3 >>>   L: 4 R: 4 mnlen: 3 mxlen: 3
Edge: 9 -> 7
Node 7 >>>   L: 5 R: 6 mnlen: 3 mxlen: 3
Edge: 7 -> 4
Node 4 >>>   L: 5 R: 5 mnlen: 4 mxlen: 8
Edge: 7 -> 5
Node 5 >>>   L: 6 R: 6 mnlen: 2 mxlen: 6

#include "bits/stdc++.h"

#pragma GCC optimize("Ofast")
#pragma GCC targetr("avx2")

using namespace std;

using ll = long long;
using pii = pair<int, int>;

using vi = vector<int>;
#define sz(x) (int)(x.size())
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for (int i = (a); i < (b); i++)

struct SuffixArray {
	vi sa, lcp;
	SuffixArray(string &s, int lim = 256) {
		int n = sz(s) + 1, k = 0, a, b;
		vi x(all(s) + 1), y(n), ws(max(n, lim)), rank(n);
		sa = lcp = y, iota(all(sa), 0);
		for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
			p = j, iota(all(y),  n - j);
			rep(i,0,n) if (sa[i] >= j) y[p++] = sa[i] - j;
			fill(all(ws), 0);
			rep(i,0,n) ws[x[i]]++;
			rep(i,1,lim) ws[i] += ws[i - 1];
			for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
			swap(x, y), p = 1, x[sa[0]] = 0;
			rep(i, 1, n) a = sa[i - 1], b = sa[i], x[b] = 
				(y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1: p++;			
		}
		rep(i, 1, n) rank[sa[i]] = i;
		for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
			for (k && k--, j = sa[rank[i] - 1];
				s[i + k] == s[j + k]; k++);
	}
};

struct DSU {
	int n;
	vector<int> dsu;
	vector<int> mn, mx;
	DSU(int _n) {
		n = _n;
		dsu.resize(n);
		mn.resize(n), mx.resize(n);
		iota(dsu.begin(), dsu.end(), 0);
		iota(mn.begin(), mn.end(), 0);
		iota(mx.begin(), mx.end(), 0);

	}

	int find(int x) {
		if (dsu[x]) return x;
		else return dsu[x] = find(dsu[x]);
	}

	void uni(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y) return;

		dsu[y] = x;
		mx[x] = max(mx[x], mx[y]);
		mn[x] = min(mn[x], mn[y]);
	}
};

const int MAXN = 500005;

void solve(int TC) {
	string s;
	cin >> s;

	SuffixArray SA(s);
	int n = s.size();

	DSU dsu(n + 1);

	struct Node {
		int L, R;
		int mnlen, mxlen;
	};

	vector<vector<int>> g;
	vector<Node> nde;

	vector<int> nodepnt(n + 1, -1);	
	vector<vector<int>> merge(MAXN);

	for (int i = 1; i <= n; i++) {
		cout << "SA: " << SA.sa[i] << " lcp: " << SA.lcp[i] << endl;
		if (i > 1) {
			merge[SA.lcp[i]].push_back(i - 1);
		}

		int len = n - SA.sa[i];
		nodepnt[i] = nde.size();
		nde.push_back({i, i, len + 1, len + 1});
		g.push_back({});
	}

	for (int i = MAXN - 1; i >= 0; i--) {
		int sz = (int)merge[i].size();
		for (int j = 0; j < sz; j++) {
			vector<int> vec;

			int x = merge[i][j], y = x + 1;
			x = dsu.find(x), y = dsu.find(y);
		
			vec.push_back(nodepnt[x]);
			vec.push_back(nodepnt[y]);
			dsu.uni(x, y);

			while (j + 1 < sz && merge[i][j + 1] == dsu.mx[x]) {
				++j;
				y = merge[i][j] + 1;
				y = dsu.find(y);
				vec.push_back(nodepnt[y]);

				dsu.uni(x, y);
			}

			int id = nde.size();
			nodepnt[x] = id;
			nde.push_back({dsu.mn[x], dsu.mx[x], i, i});
			g.push_back({});
			for (auto ch: vec) {
				nde[ch].mnlen = i + 1;
				g[id].push_back(ch);
			}
		}
	}

	int S = (int)nde.size() - 1;

	auto dfs = [&](auto &&dfs, int u, int p) -> void {
		cout << "Node " << u << " >>>   L: " << nde[u].L << " R: " << nde[u].R << " mnlen: " << nde[u].mnlen << " mxlen: " << nde[u].mxlen << endl;
		for (auto v: g[u]) {
			if (v == p) continue;
			cout << "Edge: " << u << " -> " << v << endl;
			dfs(dfs, v, u);
		}
	};
	dfs(dfs, S, -1);

}

int32_t main() {
	cin.tie(0)->sync_with_stdio(0);
	cout << fixed << setprecision(10);

	int t = 1;
	// cin >> t;
	for (int i = 1; i <= t; i++) {
		solve(i);
	}
}
Source code, Language: C++17

Details 

answer.code:22:2: error: extended character  is not valid in an identifier
   22 |     ~/De/cp/icpc/2022-byte-dance  cd "/Users/ethen/Desktop/cp/icpc/2022-byte-dance/" && g++ -g -std=c++17 -fs
      |  ^
answer.code:22:4: error: extended character  is not valid in an identifier
   22 |     ~/De/cp/icpc/2022-byte-dance  cd "/Users/ethen/Desktop/cp/icpc/2022-byte-dance/" && g++ -g -std=c++17 -fs
      |    ^
answer.code:22:6: error: extended character  is not valid in an identifier
   22 |     ~/De/cp/icpc/2022-byte-dance  cd "/Users/ethen/Desktop/cp/icpc/2022-byte-dance/" && g++ -g -std=c++17 -fs
      |      ^
answer.code:22:37: error: extended character  is not valid in an identifier
   22 |     ~/De/cp/icpc/2022-byte-dance  cd "/Users/ethen/Desktop/cp/icpc/2022-byte-dance/" && g++ -g -std=c++17 -fs
      |                                     ^
answer.code:25:2: error: extended character  is not valid in an identifier
   25 |     ~/De/cp/icpc/2022-byte-dance  ./D < D1.in                                               ✔  16:03:53 
      |  ^
answer.code:25:4: error: extended character  is not valid in an identifier
   25 |     ~/De/cp/icpc/2022-byte-dance  ./D < D1.in                                               ✔  16:03:53 
      |    ^
answer.code:25:6: error: extended character  is not valid in an identifier
   25 |     ~/De/cp/icpc/2022-byte-dance  ./D < D1.in                                               ✔  16:03:53 
      |      ^
answer.code:25:37: error: extended character  is not valid in an identifier
   25 |     ~/De/cp/icpc/2022-byte-dance  ./D < D1.in                                               ✔  16:03:53 
      |                                     ^
answer.code:25:96: error: extended character  is not valid in an identifier
   25 |     ~/De/cp/icpc/2022-byte-dance  ./D < D1.in                                               ✔  16:03:53 
      |                                                                                                ^
answer.code:25:98: error: extended character ✔ is not valid in an identifier
   25 |     ~/De/cp/icpc/2022-byte-dance  ./D < D1.in                                               ✔  16:03:53 
      |                                                                                                  ^
answer.code:25:100: error: extended character  is not valid in an identifier
   25 |     ~/De/cp/icpc/2022-byte-dance  ./D < D1.in                                               ✔  16:03:53 
      |                                                                                                    ^
answer.code:25:111: error: extended character  is not valid in an identifier
   25 |     ~/De/cp/icpc/2022-byte-dance  ./D < D1.in                                               ✔  16:03:53 
      |                                                                                                               ^
answer.code:1:1: error: ‘SA’ does not name a type
    1 | SA: 6 lcp: 0
      | ^~
In file included from /usr/include/c++/11/cmath:43,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:47:
/usr/include/c++/11/ext/type_traits.h:162:35: error: ‘bool __gnu_cxx::__is_null_pointer’ redeclared as different kind of entity
  162 |   __is_null_pointer(std::nullptr_t)
      |                                   ^
/usr/include/c++/11/ext/type_traits.h:157:5: note: previous declaration ‘template<class _Type> bool __gnu_cxx::__is_null_pointer(_Type)’
  157 |     __is_null_pointer(_Type)
      |     ^~~~~~~~~~~~~~~~~
/usr/include/c++/11/ext/type_traits.h:162:26: error: ‘nullptr_t’ is not a member of ‘std’
  162 |   __is_null_pointer(std::nullptr_t)
      |                          ^~~~~~~~~
In file included from /usr/include/c++/11/bits/move.h:57,
                 from /usr/include/c++/11/bits/stl_pair.h:59,
                 from /usr/include/c++/11/bits/stl_algobase.h:64,
                 from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from answer.code:47:
/usr/include/c++/11/type_traits:405:26: error: ‘std::size_t’ has not been declared
  405 |   template<typename _Tp, std::size_t _Size>
      |                          ^~~
/usr/include/c++/11/type_traits:406:25: error: ‘_Size’ was not declared in this scope
  406 |     struct is_array<_Tp[_Size]>
      |                         ^~~~~
/usr/include/c++/11/type_traits:406:31: error: template argument 1 is invalid
  406 |     struct is_array<_Tp[_Size]>
      |                               ^
/usr/include/c++/11/type_traits:511:42: error: ‘nullptr_t’ is not a member of ‘std’
  511 |     struct __is_null_pointer_helper<std::nullptr_t>
      |                                          ^~~~~~~~~
/usr/include/c++/11/type_traits:511:51: error: template argume...
English 繁體中文 简体中文

Server Time: 2024-11-30 07:38:33 | OpenSource Project