Submission #909093

#	Time	Username	Problem	Language	Result	Execution time	Memory
909093		lighton	Amusement Park (CEOI19_amusementpark)	C++17	19 / 100	35 ms	35828 KiB

amusementpark

#include<bits/stdc++.h>
#define forf(i,a,b) for(int i = a; i<=b; i++)
#define all(v) v.begin(),v.end()
using namespace std;
typedef long long ll;
int N,M;
pair<int,int> edge[100001];
ll mod1 = 10000007;
ll mod2 = 20000009;
ll mod3 = 30000011;
ll mod = 998244353;
vector<int> perm;
//unordered_set<ll> s1,s2;
int chk1[10000007];
int chk2[20000009];
int chk3[30000011];
int main(){
    scanf("%d %d" , &N , &M);
    forf(i,1,M){
        scanf("%d %d" , &edge[i].first,&edge[i].second);
    }
    forf(i,1,N) perm.push_back(i);
    ll ans = 0;
    do{
        ll hash1 = 0;  ll hash2 = 0; ll hash3 = 0;
        ll cnt = 0;
        forf(i,1,M){
            hash1 *= 2; hash2 *= 2; hash3 *= 2;
            if(perm[edge[i].first-1] > perm[edge[i].second-1]){
                hash1++; hash2++; hash3++;
                cnt++;
            }
            hash1 %= mod1;hash2 %= mod2;hash3 %= mod3;
        }
        if(chk1[hash1] == 0 && chk2[hash2] == 0 && chk3[hash3] == 0){
            ans += cnt;
            ans %= mod;
        }
        chk1[hash1] = 1; chk2[hash2] = 1; chk3[hash3] = 1;
    } while((next_permutation(all(perm))));
    printf("%lld" , ans);
}

Compilation message (stderr)

amusementpark.cpp: In function 'int main()':
amusementpark.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%d %d" , &N , &M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
amusementpark.cpp:20:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |         scanf("%d %d" , &edge[i].first,&edge[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 12 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 21
• Subtask 5: 0 / 37