题解 CF960F 【Pathwalks】

越学越掂 · 2018-11-02 10:46:03 · 题解

STL练手的好题，STL大杂烩

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp[100009];
map<int,int>::iterator it,jt;
int main() 
{
    int n,m,a,b,w,c,ans=0;
    for(scanf("%d%d",&n,&m);m--;) 
    {
        scanf("%d%d%d",&a,&b,&w),it=mp[a].lower_bound(w),it==mp[a].begin()?a=1:a=1+(--it)->second,it=mp[b].upper_bound(w),it==mp[b].begin()?c=0:c=(--it)->second;
        if(c<a) 
        for(ans=max(ans,mp[b][w]=max(mp[b][w],a)),it=mp[b].upper_bound(w); !(it==mp[b].end()||it->second>a);) 
        jt=it++,mp[b].erase(jt);//一连串的高端操作
    }
    printf("%d",ans),exit(0);
}