Submission #91355

#TimeUsernameProblemLanguageResultExecution timeMemory
91355YottaByteMarriage questions (IZhO14_marriage)C++14
14 / 100
1586 ms4732 KiB
#include <stdio.h> #include <iostream> using namespace std; #define pb push_back #define ll long long #define fr first #define sc second #define mk make_pair const int N = 1000; const int M = 500; int n, m, k, ans, d[N + 1][N + 1]; int tr, tb[N + 1][M + 1]; string t(int a, int b) { string res = ""; while(a) { res += char((a % b) + '0'); a /= b; } while(res.size() < m) res += '0'; return res; } void check(int l, int cur, int p) { if(d[l][cur]) { //puts("BEEN HERE\n"); return; } if(p == tr) { d[l][cur] = 1; ans += (n - cur + 1); //puts("GOTCHA"); //cout << cur << " " << t(p, 2) << endl << endl; return; } if(cur == n) { //found = true; //puts("TRY\n"); return; } int cho = 0; for(int i = 0; i < m; i++) { if(tb[i][cur]) { cho |= (1 << i); } } //cout << l << " " << cur + 1 << " " << t(cho, 2) << " " << t(p, 2) << endl; for(int i = 0; i < m; i++) { if((cho >> i) & 1) { check(l, cur + 1, (cho & (1 << i)) | p); } } } main() { scanf("%d %d %d", &n, &m, &k); for(int i = 0; i < k; i++) { int a, b; scanf("%d %d", &a, &b); a--, b--; tb[b][a] = 1; } //for(int j = 0; j < n * 2; j++) //cout << '-'; //puts(""); //for(int i = 0; i < m; i++) //{ //for(int j = 0; j < n; j++) //{ //if(tb[i][j]) cout << "+"; //else cout << " "; //cout << "|"; //} //puts(""); //for(int j = 0; j < n * 2; j++) //cout << '-'; //puts(""); //} if(n < m) { puts("0"); return 0; } tr = (1 << m) - 1; for(int l = 0; l < n; l++) { //puts("START"); check(l, l, 0); } printf("%d", ans); } /** 5 3 7 1 1 1 2 1 3 2 3 3 2 4 2 5 1 **/

Compilation message (stderr)

marriage.cpp: In function 'std::__cxx11::string t(int, int)':
marriage.cpp:26:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(res.size() < m)
        ~~~~~~~~~~~^~~
marriage.cpp: At global scope:
marriage.cpp:76:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
marriage.cpp: In function 'int main()':
marriage.cpp:78:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &m, &k);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
marriage.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a, &b);
   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...