Run ID 作者 问题 语言 测评结果 分数 时间 内存 代码长度 提交时间
52605 AK2022071305 木板游戏 C++ 运行超时 60 2000 MS 395896 KB 963 2022-07-19 13:53:24

Tests(12/20):


#include <bits/stdc++.h> using namespace std; const int maxn = 5e5+100; vector<int> adj[maxn]; int n,l[maxn],r[maxn],ans,in[maxn],len[maxn]; bool vis[maxn]; int solve (int u, int fa) { // printf("%d ",u); vis[u] = true; int ret = 1; if (!len[u]) { for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i]; if (v != fa) ret = max(ret, solve(v,u)+1); } len[u] = ret; } else { ret = len[u]; } return ret; } int main() { scanf("%d",&n); for (int i = 1; i <= n; i++) scanf("%d%d",&l[i],&r[i]); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) continue; if (l[i] <= l[j] && r[i] >= r[j]) { in[j]++; adj[i].push_back(j); } } } for (int i = 1; i <= n; i++) { if (!in[i]) { ans = max(ans, solve(i,0)); // printf("\n"); } } // for (int i = 1; i <= n; i++) { // printf("%d ", len[i]); // } // printf("\n"); printf("%d\n",ans); return 0; }


测评信息: