QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #607259 | #8941. Even or Odd Spanning Tree | AAA___# | TL | 4ms | 26204kb | C++20 | 7.5kb | 2024-10-03 14:30:24 | 2024-10-03 14:30:26 |
Judging History
answer
#include<iostream>
#include<algorithm>
#include<stack>
#include<set>
#include<unordered_set>
#include<queue>
#include<deque>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<map>
#include<string>
#include<vector>
#include<array>
#include<functional>
using namespace std;
typedef long long ll;
ll highbit(ll x){
ll ans=1;
int num=0;
while(x){
x>>=1;
ans<<=1;
num++;
}
return num;
}
ll lowbit(ll x){
return x&(-x);
}
long long max(long long a,long long b){
return a>b?a:b;
}
long long min(long long a,long long b){
return a>b?b:a;
}
ll gcd(ll x,ll y)
{
if(y==0)
return x;
return gcd(y,x%y);
}
const int maxn=5e5+10;
int ans[maxn];
struct edge{
int u,v;
ll val;
int flag;
int id;
bool operator<(const edge&an){
return val<an.val;
}
};
vector<int> G[maxn];
vector<int> W[maxn];
vector<int> ID[maxn];
edge E[maxn];
struct Kruskal{
int fa[maxn];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void init(int n,int m){
for(int i=1;i<=n;i++){
fa[i]=i;
}
sort(E+1,E+1+m);
}
bool GreatTree(int n,int m){
n--;
int l=1;
while(n--){
while(l<=m&&find(E[l].u)==find(E[l].v)){
l++;
}
if(l>m){
return false;
}
G[E[l].u].push_back(E[l].v);
W[E[l].u].push_back(E[l].val);
ID[E[l].u].push_back(E[l].id);
G[E[l].v].push_back(E[l].u);
W[E[l].v].push_back(E[l].val);
ID[E[l].v].push_back(E[l].id);
E[l].flag=1;
fa[find(E[l].u)]=find(E[l].v);
l++;
}
return true;
}
}Kal;
const int inf=1e9+5;
struct LCA{
int dep[maxn],fa[maxn][21];
int mx[maxn][21];
int mi[maxn][21];
int faid[maxn];
int log[21];
int lca(int a,int b){
if(a==b){
return a;
}
if(dep[a]<dep[b]){
int k=a;
a=b;
b=k;
}
for(int i=19;i>=0;i--){
if(dep[fa[a][i]]>=dep[b]){
a=fa[a][i];
}
if(dep[a]==dep[b]){
break;
}
}
if(a==b){
return a;
}
for(int i=19;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
void dfs(int x,int pre,int d){
dep[x]=d;
int nk=0;
for(auto i:G[x]){
if(i==pre){
nk++;
continue;
}
fa[i][0]=x;
mx[i][0]=W[x][nk];
if(W[x][nk]%2!=0){
mx[i][0]=0;
}
faid[i]=ID[x][nk];
nk++;
dfs(i,x,d+1);
}
return;
}
void init(int n){
dfs(1,0,0);
fa[1][0]=0;
dep[0]=-1;
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++){
if(fa[j][i-1]==0){
continue;
}
fa[j][i]=fa[fa[j][i-1]][i-1];
mx[j][i]=max(mx[j][i-1],mx[fa[j][i-1]][i-1]);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<20;j++){
mi[i][j]=1e9+5;
}
}
log[0]=1;
for(int i=1;i<20;i++){
log[i]=log[i-1]*2;
}
}
int getmx(int a,int b){
if(a==b){
return 0;
}
int nowdis=dep[a]-dep[b];
int buff;
int ans=0;
while(buff=highbit(nowdis)){
buff--;
ans=max(ans,mx[a][buff]);
a=fa[a][buff];
nowdis-=log[buff];
}
return ans;
}
}Lca0;
struct LCAK{
int dep[maxn],fa[maxn][21];
int mx[maxn][21];
int mi[maxn][21];
int faid[maxn];
int log[21];
int lca(int a,int b){
if(a==b){
return a;
}
if(dep[a]<dep[b]){
int k=a;
a=b;
b=k;
}
for(int i=19;i>=0;i--){
if(dep[fa[a][i]]>=dep[b]){
a=fa[a][i];
}
if(dep[a]==dep[b]){
break;
}
}
if(a==b){
return a;
}
for(int i=19;i>=0;i--){
if(fa[a][i]!=fa[b][i]){
a=fa[a][i];
b=fa[b][i];
}
}
return fa[a][0];
}
void dfs(int x,int pre,int d){
dep[x]=d;
int nk=0;
for(auto i:G[x]){
if(i==pre){
nk++;
continue;
}
fa[i][0]=x;
mx[i][0]=W[x][nk];
if(W[x][nk]%2==0){
mx[i][0]=0;
}
faid[i]=ID[x][nk];
nk++;
dfs(i,x,d+1);
}
return;
}
void init(int n){
dfs(1,0,0);
fa[1][0]=0;
dep[0]=-1;
for(int i=1;i<20;i++){
for(int j=1;j<=n;j++){
if(fa[j][i-1]==0){
continue;
}
fa[j][i]=fa[fa[j][i-1]][i-1];
mx[j][i]=max(mx[j][i-1],mx[fa[j][i-1]][i-1]);
}
}
for(int i=1;i<=n;i++){
for(int j=0;j<20;j++){
mi[i][j]=1e9+5;
}
}
log[0]=1;
for(int i=1;i<20;i++){
log[i]=log[i-1]*2;
}
}
int getmx(int a,int b){
if(a==b){
return 0;
}
int nowdis=dep[a]-dep[b];
int buff;
int ans=0;
while(buff=highbit(nowdis)){
buff--;
ans=max(ans,mx[a][buff]);
a=fa[a][buff];
nowdis-=log[buff];
}
return ans;
}
}Lca1;
int T(void){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>E[i].u>>E[i].v>>E[i].val;
E[i].id=i;
E[i].flag=0;
}
Kal.init(n,m);
if(!Kal.GreatTree(n,m)){
cout<<-1<<" "<<-1<<endl;
return 0;
}
Lca0.init(n);
Lca1.init(n);
ll ans=0;
for(int i=1;i<=m;i++){
if(E[i].flag==1){
ans+=E[i].val;
}
}
ll diff=1e9;
for(int i=1;i<=m;i++){
if(E[i].flag==0){
int u=E[i].u;
int v=E[i].v;
ll now=0;
int fa=Lca0.lca(u,v);
if(E[i].val%2==1){
now=max(Lca0.getmx(u,fa),Lca0.getmx(v,fa));
}else{
now=max(Lca1.getmx(u,fa),Lca1.getmx(v,fa));
}
if(now==0){
continue;
}
diff=min(diff,E[i].val-now);
}
}
ll ans2=ans+diff;
if(ans%2==0){
cout<<ans<<" ";
if(ans2>=1e9){
cout<<-1<<endl;
}else{
cout<<ans2<<endl;
}
}else{
if(ans2>=1e9){
cout<<-1<<" ";
}else{
cout<<ans2<<" ";
}
cout<<ans<<endl;
}
for(int i=1;i<=n;i++){
G[i].clear();
W[i].clear();
ID[i].clear();
}
return 0;
}
int main(void){
unsigned int t;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
//freopen("input.in","r",stdin);
cin>>t;
//t=1;
while(t--){
T();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 26204kb
input:
3 2 1 1 2 5 3 1 1 3 1 4 4 1 2 1 1 3 1 1 4 1 2 4 2
output:
-1 5 -1 -1 4 3
result:
ok 6 numbers
Test #2:
score: -100
Time Limit Exceeded
input:
10000 16 50 1 2 649251632 2 3 605963017 3 4 897721528 4 5 82446151 5 6 917109168 6 7 79647183 7 8 278566178 7 9 573504723 3 10 679859251 8 11 563113083 1 12 843328546 10 13 594049160 11 14 997882839 7 15 569431750 2 16 244494799 16 7 960172373 13 4 317888322 13 3 446883598 9 3 678142319 5 8 43208692...
output:
3140067932 -1 1262790434 -1 1263932600 -1 -1 1180186165 2248358640 -1 -1 3738936375 -1 1058677117 -1 3402127725 -1 1187873655 1395482806 -1 3456885934 -1 3943951826 -1 2479987500 -1 2909126794 -1 2483103706 -1 -1 1824129583 3769162572 -1 562142376 537074351 -1 2475481185 1133556832 -1