Submission #918357
Source Code Expand
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>
using namespace std;
typedef unsigned uint;
typedef long long Int;
typedef unsigned long long UInt;
const int INF = 1001001001;
const Int INFLL = 1001001001001001001LL;
template<typename T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<typename T> void chmin(T& a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T& a, T b) { if (a < b) a = b; }
int in() { int x; scanf("%d", &x); return x; }
double fin() { double x; scanf("%lf", &x); return x; }
Int lin() { Int x; scanf("%lld", &x); return x; }
char S[500000];
int M[100050][26][26], PF[100050];
struct trie {
int nxt[26], num, id;
trie() { fill(nxt, nxt + 26, -1); num = 0; id = -1; }
} T[500000];
int tnum = 1, troot = 0;
int alloc() {
return tnum++;
}
void trie_add(char* s, int id) {
int p = troot;
for (int i = 0; s[i]; ++i) {
int c = s[i] - 'a';
++T[p].num;
if (T[p].nxt[c] == -1) {
T[p].nxt[c] = alloc();
}
p = T[p].nxt[c];
}
++T[p].num;
T[p].id = id;
}
int CM[26][26];
void trie_precalc(int p, int pf) {
if (T[p].id >= 0) {
PF[T[p].id] = pf;
memcpy(M[T[p].id], CM, sizeof(CM));
++pf;
}
for (int i = 0; i < 26; ++i) {
if (T[p].nxt[i] >= 0) {
for (int j = 0; j < 26; ++j) {
if (i != j && T[p].nxt[j] >= 0) {
CM[i][j] += T[T[p].nxt[j]].num;
}
}
trie_precalc(T[p].nxt[i], pf);
for (int j = 0; j < 26; ++j) {
if (i != j && T[p].nxt[j] >= 0) {
CM[i][j] -= T[T[p].nxt[j]].num;
}
}
}
}
}
int main() {
int N = in();
for (int i = 0; i < N; ++i) {
scanf("%s", S);
trie_add(S, i);
}
trie_precalc(troot, 0);
int Q = in();
char A[32];
int O[32];
for (int i = 0; i < Q; ++i) {
int k = in() - 1;
scanf("%s", A);
for (int j = 0; j < 26; ++j) {
O[A[j] - 'a'] = j;
}
int res = 1 + PF[k];
for (int a = 0; a < 26; ++a) {
for (int b = 0; b < 26; ++b) {
if (a != b && O[a] > O[b]) {
res += M[k][a][b];
}
}
}
printf("%d\n", res);
}
return 0;
}
Submission Info
Submission Time
2016-10-10 13:41:05+0900
Task
E - Lexicographical disorder
User
japlj
Language
C++14 (GCC 5.4.1)
Score
1100
Code Size
2587 Byte
Status
AC
Exec Time
689 ms
Memory
320000 KB
Compile Error
./Main.cpp: In function ‘int in()’:
./Main.cpp:34:34: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
int in() { int x; scanf("%d", &x); return x; }
^
./Main.cpp: In function ‘double fin()’:
./Main.cpp:35:42: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
double fin() { double x; scanf("%lf", &x); return x; }
^
./Main.cpp: In function ‘Int lin()’:
./Main.cpp:36:37: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
Int lin() { Int x; scanf("%lld", &x); return x; }
^
./Main.cpp: In function ‘int main()’:
./Main.cpp:92:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%s", S);...
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1100 / 1100
Status
Set Name
Test Cases
Sample
s1.txt, s2.txt
All
01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, s1.txt, s2.txt
Case Name
Status
Exec Time
Memory
01.txt
AC
689 ms
320000 KB
02.txt
AC
689 ms
320000 KB
03.txt
AC
688 ms
320000 KB
04.txt
AC
689 ms
320000 KB
05.txt
AC
539 ms
161280 KB
06.txt
AC
431 ms
65920 KB
07.txt
AC
420 ms
57984 KB
08.txt
AC
418 ms
55936 KB
09.txt
AC
415 ms
55808 KB
10.txt
AC
419 ms
59904 KB
11.txt
AC
454 ms
135040 KB
12.txt
AC
500 ms
171008 KB
13.txt
AC
552 ms
211840 KB
14.txt
AC
421 ms
65920 KB
15.txt
AC
410 ms
55680 KB
16.txt
AC
415 ms
59904 KB
17.txt
AC
435 ms
74240 KB
18.txt
AC
354 ms
57728 KB
19.txt
AC
354 ms
57728 KB
20.txt
AC
355 ms
57728 KB
21.txt
AC
354 ms
57728 KB
22.txt
AC
353 ms
57728 KB
23.txt
AC
488 ms
158336 KB
24.txt
AC
454 ms
133760 KB
25.txt
AC
498 ms
169728 KB
26.txt
AC
354 ms
57728 KB
27.txt
AC
371 ms
65792 KB
28.txt
AC
378 ms
69888 KB
29.txt
AC
362 ms
56832 KB
30.txt
AC
432 ms
103040 KB
31.txt
AC
376 ms
58624 KB
32.txt
AC
365 ms
55808 KB
33.txt
AC
375 ms
57600 KB
34.txt
AC
371 ms
56704 KB
35.txt
AC
378 ms
56064 KB
36.txt
AC
685 ms
320000 KB
37.txt
AC
392 ms
64640 KB
38.txt
AC
392 ms
64640 KB
39.txt
AC
66 ms
54912 KB
40.txt
AC
66 ms
54912 KB
s1.txt
AC
66 ms
54912 KB
s2.txt
AC
65 ms
54912 KB