QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134476 | #6404. Shuttle Tour | nikolapesic2802 | TL | 456ms | 347992kb | C++14 | 6.8kb | 2023-08-03 20:46:06 | 2023-08-03 20:46:09 |
Judging History
answer
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
#define ll long long
#define pb push_back
#define f first
#define s second
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL)
#define ld long double
#define li __int128
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>; ///find_by_order(),order_of_key()
template<int D, typename T>struct vec : public vector<vec<D - 1, T>> {template<typename... Args>vec(int n = 0, Args... args) : vector<vec<D - 1, T>>(n, vec<D - 1, T>(args...)) {}};
template<typename T>struct vec<1, T> : public vector<T> {vec(int n = 0, T val = T()) : vector<T>(n, val) {}};
template<class T1,class T2> ostream& operator<<(ostream& os, const pair<T1,T2>& a) { os << '{' << a.f << ", " << a.s << '}'; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const deque<T>& a){os << '{';for(int i=0;i<sz(a);i++){if(i>0&&i<sz(a))os << ", ";os << a[i];}os<<'}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const set<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T> ostream& operator<<(ostream& os, const multiset<T,greater<T> >& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
template<class T1,class T2> ostream& operator<<(ostream& os, const map<T1,T2>& a) {os << '{';int i=0;for(auto p:a){if(i>0&&i<sz(a))os << ", ";os << p;i++;}os << '}';return os;}
int ri(){int x;scanf("%i",&x);return x;}
void rd(int&x){scanf("%i",&x);}
void rd(long long&x){scanf("%lld",&x);}
void rd(double&x){scanf("%lf",&x);}
void rd(long double&x){scanf("%Lf",&x);}
void rd(string&x){cin>>x;}
void rd(char*x){scanf("%s",x);}
template<typename T1,typename T2>void rd(pair<T1,T2>&x){rd(x.first);rd(x.second);}
template<typename T>void rd(vector<T>&x){for(T&p:x)rd(p);}
template<typename C,typename...T>void rd(C&a,T&...args){rd(a);rd(args...);}
//istream& operator>>(istream& is,__int128& a){string s;is>>s;a=0;int i=0;bool neg=false;if(s[0]=='-')neg=true,i++;for(;i<s.size();i++)a=a*10+s[i]-'0';if(neg)a*=-1;return is;}
//ostream& operator<<(ostream& os,__int128 a){bool neg=false;if(a<0)neg=true,a*=-1;ll high=(a/(__int128)1e18);ll low=(a-(__int128)1e18*high);string res;if(neg)res+='-';if(high>0){res+=to_string(high);string temp=to_string(low);res+=string(18-temp.size(),'0');res+=temp;}else res+=to_string(low);os<<res;return os;}
const int N=2e5+5,L=18;
int up[N][L];
int dep[N];
ll depw[N];
vector<bool> vis(N);
vector<vector<pair<int,int>>> graf(N);
vector<int> order(N);
int cntOrd=0;
vector<int> leaves;
vector<int> indl(N);
vector<int> paths[50];
int dfs(int tr){
order[tr]=cntOrd++;
vis[tr]=1;
int indx=-1;
for(auto p:graf[tr]){
if(!vis[p.f]){
dep[p.f]=dep[tr]+1;
depw[p.f]=depw[tr]+p.s;
up[p.f][0]=tr;
int a=dfs(p.f);
if(indx==-1){
indx=a;
}
}
}
if(indx==-1){
leaves.pb(tr);
indx=sz(leaves)-1;
}
indl[tr]=indx;
paths[indx].pb(tr);
return indx;
}
int lcapath[50][50];
int lca(int a,int b){
if(dep[a]<dep[b]){
swap(a,b);
}
for(int j=L-1;j>=0;j--){
if(dep[a]-dep[b]>=(1<<j)){
a=up[a][j];
}
}
if(a==b)
return a;
for(int j=L-1;j>=0;j--){
if(up[a][j]!=up[b][j]){
a=up[a][j];
b=up[b][j];
}
}
return up[a][0];
}
int lca2(int a,int b){
int A=indl[a],B=indl[b];
if(A!=B){
return lcapath[A][B];
}
return dep[a]<dep[b]?a:b;
}
int upc(int a,int k){
for(int j=L-1;j>=0;j--){
if(k>=(1<<j)){
a=up[a][j];
k-=1<<j;
}
}
return a;
}
string s;
int mn[50][4*N],mx[50][4*N];
void init(int ind,int l=0,int r=N-1,int i=1){
if(l==r){
if(s[l]=='1'&&indl[l]==ind){
//printf("%i: %i\n",ind,l);
mn[ind][i]=mx[ind][i]=dep[l];
}
else{
mn[ind][i]=N;
mx[ind][i]=0;
}
return;
}
int m=(l+r)>>1;
init(ind,l,m,2*i);
init(ind,m+1,r,2*i+1);
mn[ind][i]=min(mn[ind][2*i],mn[ind][2*i+1]);
mx[ind][i]=max(mx[ind][2*i],mx[ind][2*i+1]);
}
void flip(int ind,int p,int l=0,int r=N-1,int i=1){
if(l==r){
//printf("flip %i %i\n",ind,p);
if(s[l]=='1'){
s[l]='0';
mn[ind][i]=N;
mx[ind][i]=0;
}
else{
s[l]='1';
mn[ind][i]=mx[ind][i]=dep[l];
}
return;
}
int m=(l+r)>>1;
if(p<=m){
flip(ind,p,l,m,2*i);
}
else{
flip(ind,p,m+1,r,2*i+1);
}
mn[ind][i]=min(mn[ind][2*i],mn[ind][2*i+1]);
mx[ind][i]=max(mx[ind][2*i],mx[ind][2*i+1]);
}
pair<int,int> get(int ind,int qs,int qe,int l=0,int r=N-1,int i=1){
if(qs>r||qe<l){
return {N,0};
}
if(qs<=l&&qe>=r){
return {mn[ind][i],mx[ind][i]};
}
int m=(l+r)>>1;
auto a=get(ind,qs,qe,l,m,2*i);
auto b=get(ind,qs,qe,m+1,r,2*i+1);
return {min(a.f,b.f),max(a.s,b.s)};
}
int main()
{
int n=ri(),q=ri();
cin >> s;
while(sz(s)<N){
s+='0';
}
for(int i=1;i<n;i++){
int u=ri()-1,v=ri()-1,w=ri();
graf[u].pb({v,w});
graf[v].pb({u,w});
}
dep[0]=0;
depw[0]=0;
up[0][0]=0;
dfs(0);
for(int j=1;j<L;j++){
for(int i=0;i<n;i++){
up[i][j]=up[up[i][j-1]][j-1];
}
}
int m=sz(leaves);
for(int i=0;i<m;i++){
for(int j=0;j<m;j++){
lcapath[i][j]=lca(leaves[i],leaves[j]);
}
}
for(int j=0;j<m;j++){
init(j);
}
while(q--){
int t=ri();
if(t==1){
int x=ri()-1;
flip(indl[x],x);
}
else{
int l=ri()-1,r=ri()-1;
vector<int> dots;
for(int j=0;j<m;j++){
auto a=get(j,l,r);
if(a.f<=a.s){
int depl=dep[leaves[j]];
dots.pb(paths[j][depl-a.f]);
if(a.f!=a.s)
dots.pb(paths[j][depl-a.s]);
}
}
if(sz(dots)==0){
printf("-1\n");
}
else{
vector<pair<int,int>> ord;
for(auto p:dots){
ord.pb({order[p],p});
}
//cout << ord << endl;
sort(all(ord));
ll dist=0;
for(int i=0;i<sz(ord);i++){
int j=(i+1)%sz(ord);
int l=lca(ord[i].s,ord[j].s);
//printf("%i %i %i\n",ord[i].s,ord[j].s,l);
dist+=depw[ord[i].s]+depw[ord[j].s]-2*depw[l];
}
printf("%lld\n",dist);
}
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 26996kb
input:
5 6 10110 1 2 1 1 3 10 2 4 100 3 5 1000 2 1 5 1 3 2 1 5 2 2 4 2 5 5 2 1 1
output:
222 202 0 -1 0
result:
ok 5 number(s): "222 202 0 -1 0"
Test #2:
score: 0
Accepted
time: 424ms
memory: 160828kb
input:
50 200000 00100100100001101010110100000111100011101110011010 14 47 940241413 11 43 331483591 37 38 496247070 47 46 832459694 7 15 16479291 1 30 402388666 30 8 513064064 46 50 739311480 5 4 761894947 32 41 631669659 17 24 715786564 35 20 763151642 32 33 492466005 39 11 186023146 9 7 805081251 3 42 25...
output:
17149847378 -1 26540740138 29613692754 21307948558 27003443184 11893407374 18332625722 20412196350 20281573062 29727468956 9593307160 9380710234 23682775470 16688997988 2856655228 14982588156 0 -1 9140136614 26193602866 22558599316 24807163344 19126284190 8533875940 7695830712 18079494744 0 27004673...
result:
ok 100000 numbers
Test #3:
score: 0
Accepted
time: 456ms
memory: 173304kb
input:
50 200000 10010001110011101101101011010011100101101010111001 1 25 560163135 2 7 696374536 33 39 14485266 39 22 456690113 4 5 267811886 18 6 657680382 3 43 865617406 25 14 885515220 41 34 919525052 42 50 410634144 8 3 487403277 3 30 701549676 2 43 54223104 7 34 691078766 14 23 323352590 26 48 4936558...
output:
17177676326 31373486130 15290175638 8192974494 22734716092 27802380120 6315957348 0 15780401446 15929384564 26423899248 9639532596 21199366790 26413065782 -1 29063665908 29925313598 28651879288 17144176262 16526083688 28206620550 26873163342 14840246174 32414950818 29985336496 0 11937422088 11131990...
result:
ok 100000 numbers
Test #4:
score: 0
Accepted
time: 418ms
memory: 160396kb
input:
50 200000 01011001001010000100001101100111011001101011101000 34 29 654100339 33 5 947063765 45 25 962067151 11 13 509130797 26 47 988757358 49 22 75267557 7 11 431530851 46 1 531969122 22 43 449891945 34 6 526679193 50 17 499004364 22 23 226725950 26 48 203414490 11 44 900725507 10 29 451714017 35 2...
output:
24080362406 0 0 21418182584 28358635244 28257750030 24520294678 21418182584 0 15335211126 28621468542 18664505530 19335499776 32374868794 23618866752 26801803500 24116134918 27676993638 30222353942 25612316674 20504702130 28400398734 29472795250 24400110084 20586186786 25612316674 0 30067400886 1297...
result:
ok 100000 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 20584kb
input:
2 10 01 1 2 340134039 2 1 2 1 1 2 1 2 1 2 2 1 1 1 2 2 2 2 1 2 2 2 2 1 1
output:
0 680268078 0 0 -1
result:
ok 5 number(s): "0 680268078 0 0 -1"
Test #6:
score: 0
Accepted
time: 113ms
memory: 62628kb
input:
200000 100 1100001001001101010000111111011011101010001011011011011010101111010001111010101100101001010000110100100011111010011100101010010001011010111100101110010000101010000100111100000011001100111101110011000011010011011011100101100111101010111101110111001111111010001010010000110110100000111000111...
output:
187263442365796 187267199881816 187176203274470 187269896250018 187239740690858 186974761323092 187257776119514 187269896250018 187035239640930 186911636122472 187263030332128 187121605387264 187264313877130 187263442365796 187269896250018 187249588971104 187263442365796 187263442365796 187264313877...
result:
ok 50 numbers
Test #7:
score: 0
Accepted
time: 151ms
memory: 66908kb
input:
200000 100 1000100001000101011000010111101000110001110111010000000010100100001110001110011001001011000010001000101111000111000100111101111111011111101101011110010101110000011011000101010000101110000100101000101110011111110000010011010010001001010001101000001111001001011111110100100011011100010100101...
output:
187406582272754 187713357625510 187713357625510 187710409039730 187708440524170 187705546874918 187675370061160 187696435101958 187704004975728 187708440524170 187708440524170 187490194913408 186797006090958 187708440524170 187708440524170 187694259450196 187691068337432 187699562335668 187708440524...
result:
ok 50 numbers
Test #8:
score: 0
Accepted
time: 231ms
memory: 347992kb
input:
200000 100 1101110101111010101100101110111101001010101100011111011010101101001011000101011011110110110001000000110000100110101010001011100110100101010110001111000100011010101011100011111010111001011110110001001010000001010100000000100010010000110100101010000111010100100111001011101001000011010101011...
output:
187071935465024 186902015424650 186944515923806 187083386398370 187083386398370 186176053533638 187210565613960 186840136921858 187059112646348 186963648681914 187157614978100 187171857507720 186687953621656 187037985042418 184267618052908 185811051686090 186716949587794 186666528269428 186754258305...
result:
ok 50 numbers
Test #9:
score: -100
Time Limit Exceeded
input:
200000 200000 1010011001010010101000001000111111110110111100000011000110010101000001101110111000100011010101100011001011101100010100000010100000100110100001000111010000011001010111001001000000111001100110010100101010111000000000011110101110010101110110110101100001011001101010101001000010000010000000...
output:
185874943612396 186901189463748 185325592077116 187007806200644 185723936146376 186683200699722 186830061692652 186256265895174 186860903405924 186810412385682 186744028102060 186994420108608 186831837842360 180459525430870 186966649455016 186952309712742 185810351127924 186849618327982 186494273101...