从若干个数中选出最大的任意两数取模之后的结果
严格次大值
对于此题
首先缩点
然后拓扑排序
维护到达每个点的最大值与严格次大值
感觉思路与代码都OK啊
then....
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <queue> #include <ctime> 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 gc const 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 <int, int> 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] << " "; 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 << " "; 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 << " "; // } // 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 << " "; // } // } 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 1 5 5 5 7 5 5 5 5 1 2 2 3 3 1 3 4 5 1 6 5 1 6 6 8 8 7 7 6 1 2 3 4 5 */