#include<bits/stdc++.h> #define f first #define s second using namespace std; int const M=1e6+21; long long ile[M]; bool B[M]; vector<pair<int,int> >Va; vector<pair<int,int> >Vb; vector<int>V; int main() { int t; cin>>t; while(t) { t--; int n; scanf("%i",&n); long long l,a,b; while(n) { n--; scanf("%lld%lld%lld",&l,&a,&b); if(!B[a])V.push_back(a); B[a]=1; if(!B[b])V.push_back(b); B[b]=1; Va.push_back({a,l}); Vb.push_back({b,l}); } sort(Va.begin(),Va.end()); sort(Vb.begin(),Vb.end()); sort(V.begin(),V.end()); int ia=Va.size()-1,ib=Vb.size()-1; while(ia>=0&&ib>=0) { long long b=Vb[ib].f; long long a=Va[ia].f; long long maly=min(Vb[ib].s,Va[ia].s); if(b>a) { ile[b]+=(a-b)*maly; Vb[ib].s-=maly; Va[ia].s-=maly; } else { ile[a]+=(a-b)*maly; Vb[ib].s-=maly; Va[ia].s-=maly; } if(Va[ia].s==0)ia--; if(Vb[ib].s==0)ib--; } for(int i=V.size()-1; i>=0; i--) { if(ile[V[i]]<0) { printf("NIE\n"); break; } if(i==0) { if(ile[V[0]]==0) printf("TAK\n"); else printf("NIE\n"); break; } ile[V[i-1]]+=ile[V[i]]; } for(int i=0; i<V.size(); i++) { B[V[i]]=0; ile[V[i]]=0; } Va.clear(); Vb.clear(); V.clear(); } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | #include<bits/stdc++.h> #define f first #define s second using namespace std; int const M=1e6+21; long long ile[M]; bool B[M]; vector<pair<int,int> >Va; vector<pair<int,int> >Vb; vector<int>V; int main() { int t; cin>>t; while(t) { t--; int n; scanf("%i",&n); long long l,a,b; while(n) { n--; scanf("%lld%lld%lld",&l,&a,&b); if(!B[a])V.push_back(a); B[a]=1; if(!B[b])V.push_back(b); B[b]=1; Va.push_back({a,l}); Vb.push_back({b,l}); } sort(Va.begin(),Va.end()); sort(Vb.begin(),Vb.end()); sort(V.begin(),V.end()); int ia=Va.size()-1,ib=Vb.size()-1; while(ia>=0&&ib>=0) { long long b=Vb[ib].f; long long a=Va[ia].f; long long maly=min(Vb[ib].s,Va[ia].s); if(b>a) { ile[b]+=(a-b)*maly; Vb[ib].s-=maly; Va[ia].s-=maly; } else { ile[a]+=(a-b)*maly; Vb[ib].s-=maly; Va[ia].s-=maly; } if(Va[ia].s==0)ia--; if(Vb[ib].s==0)ib--; } for(int i=V.size()-1; i>=0; i--) { if(ile[V[i]]<0) { printf("NIE\n"); break; } if(i==0) { if(ile[V[0]]==0) printf("TAK\n"); else printf("NIE\n"); break; } ile[V[i-1]]+=ile[V[i]]; } for(int i=0; i<V.size(); i++) { B[V[i]]=0; ile[V[i]]=0; } Va.clear(); Vb.clear(); V.clear(); } } |