Submission #95471

#TimeUsernameProblemLanguageResultExecution timeMemory
95471choikiwonMarriage questions (IZhO14_marriage)C++17
68 / 100
203 ms4600 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MN = 100010; int N, M, K; vector<int> adj[MN]; int vis[MN], who[MN], timer; vector<int> rem; bool dfs(int u, int l, int r) { if(vis[u] == timer) return false; vis[u] = timer; for(int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if(v < l || r < v) continue; if(who[v] == -1 || dfs(who[v], l, r)) { who[v] = u; return true; } } return false; } int 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--; adj[b].push_back(a); } memset(who, -1, sizeof(who)); for(int i = 0; i < M; i++) rem.push_back(i); ll ans = 0; int j = 0; for(int i = 0; i < N; i++) { while(j < N && rem.size()) { while(rem.size()) { int t = rem.back(); rem.pop_back(); timer++; if(!dfs(t, i, j)) { rem.push_back(t); break; } } j++; } if(rem.size()) break; ans += N - j + 1; if(who[i] != -1) { rem.push_back(who[i]); } } printf("%lld", ans); }

Compilation message (stderr)

marriage.cpp: In function 'bool dfs(int, int, int)':
marriage.cpp:17:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < adj[u].size(); i++) {
                    ~~^~~~~~~~~~~~~~~
marriage.cpp: In function 'int main()':
marriage.cpp:30:10: 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:33:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int a, b; scanf("%d %d", &a, &b);
                   ~~~~~^~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...