Submission #316860

#TimeUsernameProblemLanguageResultExecution timeMemory
316860ronnithLozinke (COCI17_lozinke)C++14
15 / 100
1092 ms1528 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #warning Check Integer OverFlow #define ll long long #define rep(i,a,b) for(int i=a;i<b;i++) #define maxs(a,b) if(b>a)a=b #define mins(a,b) if(b<a)a=b #define debug(x) cerr<<"["<<#x<<":"<<x<<"] " #define debug2(a,b) debug(a);debug(b) #define debug3(a,b,c) debug2(a,b);debug(c) #define de cerr #define gcd(a,b) __gcd(a,b) #define lcm(a,b) (((a)/(__gcd(a,b))) * b) #define print(arr) for(auto it = arr.begin();it < arr.end();it ++){cout << *it << " ";}cout << ln; #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> #define all(a) (a).begin(), (a).end() #define vi vector<int> #define v vector #define p pair #define pii p<int,int> #define pb push_back #define mk make_pair #define f first #define s second #define ln "\n" typedef long double ld; using namespace std; using namespace __gnu_pbds; ll modF=1e9+7; /*OUTPUT */ int N; string a[20000]; int val[20000]; int dp[20000]; struct DSU{ vi pr; vi size; DSU(int n){ pr.assign(n,0); size.assign(n,1); rep(i,0,n){ pr[i] = i; } } int root(int x){ if(pr[x] == x)return x; return pr[x] = root(pr[x]); } void unite(int x,int y){ int rx = x; int ry = y; if(rx == ry)return; if(size[rx] > size[ry]){ pr[ry] = rx; size[rx] += size[ry]; } else{ pr[rx] = ry; size[ry] += size[rx]; } } bool same(int x,int y){ if(root(x) == root(y)){ return true; } return false; } }; bool cmp(string ax,string bx){ return ax.length() < bx.length(); } bool sub(int i,int j){ int l1 = a[i].length(); int l2 = a[j].length(); for(int it = 0;it <= l1 - l2;it ++){ bool pos = true; for(int k = it;k < it + l2;k ++){ if(a[i][k] != a[j][k - it]) pos = false; } if(pos){ return true; } } return false; // int pi[l2]; // pi[0] = 0; // for(int it = 1;it < l2;it ++){ // int h = pi[it - 1]; // while(h > 0 and a[j][h] != a[j][it]){ // h = pi[h - 1]; // } // if(a[j][it] == a[j][h]){ // h ++; // } // pi[it] = h; // } // // debug2(a[i],a[j]) // // for(auto e:pi){ // // debug(e); // // } // // de << ln; // int it1 = 0; // int it2 = 0; // while(it1 < l1){ // while(it2 < l2 and it1 < l1 and a[i][it1] == a[j][it2]){ // it1 ++; // it2 ++; // } // if(it2 == 0){ // it1 ++; // continue; // } // if(it2 == l2){ // return true; // } // it2 = pi[it2 - 1]; // } // return false; } void solve(){ cin >> N; rep(i,0,N){ cin >> a[i]; val[i] = 0; } DSU d(N); sort(a,a + N,cmp); int ans = 0; for(int i = N;i >= 0;i --){ for(int j = i + 1;j < N;j ++){ if(a[i] == a[j]){ ans += 2; } else if(d.same(j,i)){ ans ++; } else if(sub(j,i)){ d.unite(j,i); ans ++; } } } cout << ans << ln; } int main(){ ios::sync_with_stdio(0);cin.tie(0); int t = 1; // cin >> t; while(t --){ solve(); } }

Compilation message (stderr)

lozinke.cpp:4:2: warning: #warning Check Integer OverFlow [-Wcpp]
    4 | #warning Check Integer OverFlow
      |  ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...