E
#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define step(x) fixed<< setprecision(x)<< #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ll long long #define endl (" ") #define ft first #define sd second #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const ll mod=1e9+7; const ll INF = 1e18+1LL; const int inf = 1e9+1e8; const double PI=acos(-1.0); const int N=2e5+100; int x[N],y[N],n,ans; bool fun(int a, int b, int c){ int x1=x[b]-x[a], y1=y[b]-y[a], x2=x[c]-x[b], y2=y[c]-y[b]; return (x1*y2-x2*y1)>=0; } int main(){ int a,b,c; cin>>n; int k=-inf; for(int i=1; i<=n; ++i){ cin>>x[i]>>y[i]; if(x[i]>=k){ b=i; k=x[i]; } } for(int i=1; i<=n; ++i){ if(i==n) a=i-1, c=1; else if(i==1) a=n, c=i+1; else a=i-1, c=i+1; if(fun(a,i,c)) ans++; } if(b==n) a=b-1, c=1; else if(b==1) a=n, c=b+1; else a=b-1, c=b+1; if(fun(a,b,c)) ans=n-ans; cout<<ans<<endl; return 0; }
F
#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define step(x) fixed<< setprecision(x)<< #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ll long long #define endl (" ") #define ft first #define sd second #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const ll mod=1e9+7; const ll INF = 1e18+1LL; const int inf = 1e9+1e8; const double PI=acos(-1.0); const int N=2e5+100; ///http://codeforces.com/gym/101081 ///FFFFFF int siz[N],son[N],dep[N],top[N],fa[N],has[N],ran[N],sson[N],cnt; struct Edge{ int to, w, next, id; bool friend operator <(Edge a, Edge b){ return a.w>b.w; } }e[N<<1]; int tot=2,head[N<<1],vis[N<<1],wi[N]; //int to[N<<1],nex[N<<1],head[N<<1],wi[N<<1],tot=2,vis[N<<1]; int n,m,q; void add(int u, int v, int w){ e[tot].to=v; e[tot].w=w; e[tot].id=tot; e[tot].next=head[u]; head[u]=tot++; } void Prime(int n){ Edge now; bool mk[N]; mem(mk,0); priority_queue<Edge> Q; while(!Q.empty()) Q.pop(); for(int i=head[1]; i; i=e[i].next) Q.push(e[i]); mk[1]=1, n--; while(n--){ now=Q.top(); Q.pop(); while(mk[now.to]){ now=Q.top(); Q.pop(); } vis[now.id]=1, vis[now.id^1]=1; wi[now.to]=now.w; mk[now.to]=1; for(int i=head[now.to]; i; i=e[i].next){ if(!mk[e[i].to]) Q.push(e[i]); } } } void dfs1(int u, int faa){ siz[u]=1; fa[u]=faa; dep[u]=dep[faa]+1; for(int i=head[u]; i; i=e[i].next){ int v=e[i].to; if(v==faa || vis[i]==0) continue; dfs1(v,u); siz[u]+=siz[v]; if(siz[son[u]]<siz[v]) son[u]=v; } } void dfs2(int u, int tp){ top[u]=tp; has[u]=++cnt; ran[cnt]=u; if(son[u]) dfs2(son[u],tp); for(int i=head[u]; i; i=e[i].next){ int v=e[i].to; if(v==fa[u] || v==son[u] || vis[i]==0) continue; dfs2(v,v); } } int mma[N][30]; struct RMQ{ int log2[N<<1]; void init(){ log2[0]=-1; for(int i = 1; i <= n; i ++) log2[i] = log2[i >> 1] + 1; for(int j = 1; j <= 25; j ++) for(int i = 1; i + (1 << j) <= n + 1; i ++) mma[i][j] = max(mma[i][j - 1], mma[i + (1 << j - 1)][j - 1]); } int query(int ql, int qr){ int k = log2[qr - ql + 1]; return max(mma[ql][k], mma[qr - (1 << k) + 1][k]); } }rmq; int get_ans(int u, int v){ int ans=0; while(top[u]!=top[v]){ if(dep[top[u]]<dep[top[v]]) swap(u,v); ans=max(ans,rmq.query(has[top[u]],has[u])); u=fa[top[u]]; } if(u==v) return ans; if(dep[u]>dep[v]) swap(u,v); return ans=max(ans,rmq.query(has[son[u]],has[v])); } int main(){ int u,v,w,a,b; scanf("%d%d",&n,&m); for(int i=1; i<=m; ++i){ scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } Prime(n); dfs1(1,1); dfs2(1,1); for(int i=1; i<=n; ++i) mma[has[i]][0]=wi[i]; rmq.init(); scanf("%d",&q); while(q--){ scanf("%d%d",&a,&b); printf("%d ",get_ans(a,b)); } return 0; }
I
#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define step(x) fixed<< setprecision(x)<< #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ll long long #define endl (" ") #define ft first #define sd second #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const ll mod=1e9+7; const ll INF = 1e18+1LL; const int inf = 1e9+1e8; const double PI=acos(-1.0); const int N=2e5+100; ///http://codeforces.com/gym/101081 struct Node{ int s, e, id; friend operator< (Node a, Node b){ return a.e<b.e; } }a[N]; vector<int> ans; int hh1,hh2,mm1,mm2,s,e; char c; int main(){ ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); int n; cin>>n; for(int i=1; i<=n; ++i){ cin>>hh1>>c>>mm1>>hh2>>c>>mm2; a[i].s=hh1*60+mm1,a[i].e=hh2*60+mm2,a[i].id=i; } sort(a+1,a+1+n); int now=0; for(int i=1; i<=n; ++i){ if(a[i].s>=now){ ans.pb(a[i].id); now=a[i].e; } } for(auto j : ans){ cout<<j<<" "; } return 0; }