Submission #973685

#TimeUsernameProblemLanguageResultExecution timeMemory
973685vjudge1Passport (JOI23_passport)C++17
0 / 100
97 ms17724 KiB
#include <time.h> #include <cstdlib> #include <stack> #include <numeric> #include <unordered_map> #include <unordered_set> #include <iomanip> #include <map> #include <set> #include <iterator> #include <deque> #include <queue> #include <sstream> #include <array> #include <string> #include <tuple> #include <chrono> #include <cassert> #include <cstdio> #include <cstring> #include <list> #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <bitset> using namespace std; int tt = 1, n; int a[200005], lf[200005], rg[200005]; int dp[200005], p[200005]; vector<int> g1[200005], g2[200005]; int main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n; for(int i = 1; i <= n; i++){ cin >> lf[i] >> rg[i]; } cin >> tt; while(tt--){ int x; cin >> x; bool ok = 0; set<pair<int, int>> st1, st2; for(int i = 1; i <= n; i++){ dp[i] = 1e9; g1[i].clear(); g2[i].clear(); p[i] = 0; } dp[x] = 0; int l = x, r = x, pos = x; st1.insert({dp[x], x}); st2.insert({dp[x], x}); g1[lf[x]].push_back(x); g2[rg[x]].push_back(x); int mn1 = l, mx1 = r; if(lf[x] == x) st1.erase({dp[x], x}); if(rg[x] == x) st2.erase({dp[x], x}); g1[x].clear(); g2[x].clear(); int l1 = lf[x], r1 = rg[x]; while(l > 1 || r < n){ bool f1 = 0, f2 = 0; int dop1 = 1e9, dop2 = 0; if(l != l1){ f1 = 1; for(int i = l - 1; i >= l1; i--){ dp[i] = st1.begin()->first + 1; p[i] = st1.begin()->second; for(int to : g1[i]) st1.erase({dp[to], to}); g1[i].clear(); if(lf[i] != i){ st1.insert({dp[i], i}); g1[lf[i]].push_back(i); } if(rg[i] > r1){ st2.insert({dp[i], i}); g2[rg[i]].push_back(i); } dop1 = min(dop1, lf[i]); dop2 = max(dop2, rg[i]); } } if(r != r1){ f2 = 1; for(int i = r + 1; i <= r1; i++){ dp[i] = st2.begin()->first + 1; p[i] = st2.begin()->second; for(int to : g2[i]) st2.erase({dp[to], to}); g2[i].clear(); if(rg[i] != i){ st2.insert({dp[i], i}); g2[rg[i]].push_back(i); } if(lf[i] < l1){ st1.insert({dp[i], i}); g1[lf[i]].push_back(i); } dop2 = max(dop2, rg[i]); dop1 = min(dop1, lf[i]); } } if(!f1 && !f2){ ok = 1; break; } if(f1 == 1) l = l1; if(f2 == 1) r = r1; l1 = min(dop1, l1), r1 = max(dop2, r1); } if(ok){ cout << -1 << "\n"; continue; } int ans = 0; set<int> st; for(int i = 1; i <= n; i++){ int x = p[i]; while(x != 0){ st.insert(x); x = p[x]; } } cout << int(st.size()) << "\n"; } }

Compilation message (stderr)

passport.cpp: In function 'int main()':
passport.cpp:55:27: warning: unused variable 'pos' [-Wunused-variable]
   55 |         int l = x, r = x, pos = x;
      |                           ^~~
passport.cpp:60:13: warning: unused variable 'mn1' [-Wunused-variable]
   60 |         int mn1 = l, mx1 = r;
      |             ^~~
passport.cpp:60:22: warning: unused variable 'mx1' [-Wunused-variable]
   60 |         int mn1 = l, mx1 = r;
      |                      ^~~
passport.cpp:121:13: warning: unused variable 'ans' [-Wunused-variable]
  121 |         int ans = 0;
      |             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...