从若干个数中选出最大的任意两数取模之后的结果

严格次大值

对于此题

首先缩点

然后拓扑排序

维护到达每个点的最大值与严格次大值

感觉思路与代码都OK啊

then....

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;#define LL long long#define gc getchar()inline int read() { int x = 0; char c = gc; while(c < '0' || c > '9') c = gc;while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}inline LL read_LL() {LL x = 0; char c = gc; while(c < '0' || c > '9') c = gc;while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc; return x;}#undef gcconst int N = 4e5 + 10, M = 2e6 + 10;int n, m, S, Q;int A[N];int Dfn[N], Low[N], Belong[N], Beljs, Tim;bool vis[N];int Stack[N], topp;pair 
             
               Pair[N];struct Node { int u, v, nxt;} G[M];int head1[N], cnt;inline void Link(int u, int v) {G[++ cnt].v = v; G[cnt].nxt = head1[u]; head1[u] = cnt;}void Tarjan(int u) { Dfn[u] = Low[u] = ++ Tim; vis[u] = 1; Stack[++ topp] = u; for(int i = head1[u]; ~ i; i = G[i].nxt) { int v = G[i].v; if(!Dfn[v]) { Tarjan(v); Low[u] = min(Low[u], Low[v]); } else if(vis[v]) Low[u] = min(Low[u], Low[v]); } if(Low[u] == Dfn[u]) { int Max = 0, CMax = 0; Max = A[u]; vis[u] = 0; Belong[u] = ++ Beljs; Pair[Beljs].first = A[u]; Pair[Beljs].second = -1; while(Stack[topp] != u) { int a = Stack[topp]; vis[a] = 0; Belong[a] = Beljs; topp --; if(A[a] > Max) {CMax = Max, Max = A[a];} else if(A[a] != Max) CMax = max(CMax, A[a]); Pair[Beljs] = make_pair(Max, CMax); } topp --; }}Node E[M];int head2[N], Du[N];inline void ReLink(int u, int v) {Du[v] ++; E[++ cnt].v = v; E[cnt].nxt = head2[u]; head2[u] = cnt;}int use[N];void Rebuild() { for(int i = 1; i <= Beljs; i ++) head2[i] = -1; cnt = 0; for(int u = 1; u <= n; u ++) for(int i = head1[u]; ~ i; i = G[i].nxt) { int v = G[i].v; if(Belong[u] != Belong[v] && use[Belong[v]] != u) { use[Belong[v]] = u;// cout << Belong[u] << " " << Belong[v] << "\n"; ReLink(Belong[u], Belong[v]); } }}int Que[N];bool beuse[N];void Topsort() { int h = 1, t = 0;// for(int i = 1; i <= Beljs; i ++) if(Du[i] == 0) Que[++ t] = i; Que[++ t] = Belong[S]; while(h <= t) { int topu = Que[h ++]; beuse[topu] = 1; for(int i = head2[topu]; ~ i; i = E[i].nxt) { int v = E[i].v; Du[v] --; if(Du[v] == 0) Que[++ t] = v; int B[5];// cout << Pair[topu].first << " " << Pair[topu].second << " " << Pair[v].first << " " << Pair[v].second << "\n"; B[1] = Pair[topu].first, B[2] = Pair[topu].second, B[3] = Pair[v].first, B[4] = Pair[v].second; sort(B + 1, B + 5); Pair[v].first = B[4]; int j = 3; while(B[j] == B[4]) j --; Pair[v].second = B[j]; } }}int main() {// srand(time(0) - 99999);// freopen("gg.in", "r", stdin);// freopen("gg.out", "w", stdout); n = read(), m = read(), Q = read(), S = read(); for(int i = 1; i <= n; i ++) A[i] = read(); for(int i = 1; i <= n; i ++) head1[i] = -1; for(int i = 1; i <= m; i ++) { int u = read(), v = read(); Link(u, v); } for(int i = 1; i <= n; i ++) if(!Dfn[i]) Tarjan(i);// for(int i = 1; i <= Beljs; i ++) {// cout << Pair[i].first << " " << Pair[i].second << "\n";// }// return 0; Rebuild();// for(int i = 1; i <= Beljs; i ++) {// for(int j = head2[i]; ~ j; j = E[j].nxt) {// int v = E[j].v;// cout << i << " " << v << "\n";// }// } Topsort(); for(int i = 1; i <= Q; i ++) { int a = read(); if(beuse[Belong[a]] == 0) cout << -1 << " "; else cout << Pair[Belong[a]].second << " "; // if(ans == 0) cout << -1 << " ";// cout << ans << " "; } return 0;}/*8 10 5 15 5 5 7 5 5 5 51 22 33 13 45 16 51 66 88 77 61 2 3 4 5*/