QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#136903#241. Chiaki Sequence RevisitedVengeful_Spirit#0 0ms0kbC++203.6kb2023-08-09 13:52:242023-08-09 13:52:25

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-09 13:52:25]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2023-08-09 13:52:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int indec;
const int mo=1e9+7;
#define int long long
struct edge{
  int u,v,l;
  int f[2][2];
  int g[2][2];
  edge(){
    memset(f,0,sizeof(f));
    for(int i:{0,1})for(int j:{0,1})f[i][j]=0;
    u = v = l=0;
  }
  edge(int uu, int vv,int ll) : u(uu), v(vv),l(ll){
    f[0][0]=0; f[0][1]=0; f[1][0]=0; f[1][1]=ll;
    g[0][0]=1; g[0][1]=0; g[1][0]=0; g[1][1]=1;
  }
  void rev(){
    swap(u,v);
    swap(f[0][1],f[1][0]);
    swap(g[0][1],g[1][0]);
  }
  pair<int,int> cal(){
    pair<int,int>ans={0,0};
    for(int i:{0,1})for(int j:{0,1}){
      ans=max(ans,{f[i][j],g[i][j]});
    }
    return ans;
  }
}t[N<<2];
set<pair<int,int>>e[N];
int merge(edge a,edge b){
  if(a.v==b.u){
  }
  else if(a.u==b.u){
    a.rev();
  }
  else if(a.v==b.v){
    b.rev();
  }
  else {
    a.rev();
    b.rev();
  }
  if(a.v!=b.u)assert(0);
  ++indec;
  t[indec].u=a.u;
  t[indec].v=b.v;
  for(int i:{0,1})for(int j:{0,1})for(int k:{0,1})for(int l:{0,1}){
    if(!(j&&k)){
      if(t[indec].f[i][l]<a.f[i][j]+b.f[k][l]){
	t[indec].f[i][l]=a.f[i][j]+b.f[k][l];
	t[indec].g[i][l]=(1ll*a.g[i][j]*b.g[k][l])%mo;

      }
      else if(t[indec].f[i][l]==a.f[i][j]+b.f[k][l]){
	t[indec].f[i][l]=a.f[i][j]+b.f[k][l];
	(t[indec].g[i][l]+=(1ll*a.g[i][j]*b.g[k][l])%mo)%=mo;
      }
    }
  }
  return indec;
}
int place(edge a,edge b){
  if(a.v!=b.v)a.rev();
  ++indec;
  t[indec].u=a.u;
  t[indec].v=a.v;
  if(a.v!=b.v)assert(0);
  for(int i:{0,1})for(int j:{0,1})for(int k:{0,1})for(int l:{0,1}){
    if(!(i&&k)&&!(j&&l)){
      if(t[indec].f[i|k][j|l]<a.f[i][j]+b.f[k][l]){
	t[indec].f[i|k][j|l]=a.f[i][j]+b.f[k][l];
	t[indec].g[i|k][j|l]=(1ll*a.g[i][j]*b.g[k][l])%mo;
      }

      else if(t[indec].f[i|k][j|l]==a.f[i][j]+b.f[k][l]){
	t[indec].f[i|k][j|l]=a.f[i][j]+b.f[k][l];
	(t[indec].g[i|k][j|l]+=(1ll*a.g[i][j]*b.g[k][l])%mo)%=mo;
      }
    }
  }
  return indec;
}
void insert(int x,int v,int c){
  auto it=e[x].lower_bound({v,0});
  if(it!=e[x].end()&&(*it).first==v){
    int pre=(*it).second;
    int cur=place(t[c],t[pre]);
    e[x].erase({v,pre});
    e[v].erase({x,pre});
    e[x].insert({v,cur});
    e[v].insert({x,cur});
  }
  else{
    e[x].insert({v,c});
    e[v].insert({x,c});
  }
}
int ban[N];
void solve(int n){
  for(int i=1;i<=n;i++)ban[i]=0;
  queue<int>q;
  for(int i=1;i<=n;i++){
    if(e[i].size()==2){
      q.push(i);
    }
  }
  while(!q.empty()){
    int x=q.front();
    q.pop();
    if(ban[x])continue;
    if(e[x].size()!=2)continue;
    ban[x]=1;
    auto it=e[x].begin();
    auto itt=it;
    ++itt;
    int e1=(*it).second;
    int e2=(*itt).second;
    int cur=merge(t[e1],t[e2]);
    e[t[cur].u].erase({x,e1});
    e[t[cur].v].erase({x,e2});
    insert(t[cur].v,t[cur].u,cur);
    if(e[t[cur].v].size()==2){
      q.push(t[cur].v);
    }
    if(e[t[cur].u].size()==2){
      q.push(t[cur].u);
    }
  }
  for(int i=1;i<=n;i++){
    if(!ban[i]){
      int x=(*e[i].begin()).second;
      auto res=t[x].cal();
      if(res.first<0)assert(0);
      if(res.second<0)assert(0);
      printf("%lld %lld\n",res.first,res.second);
      return; 
    }
  }
  assert(0);
}
signed main(){
  int T;
  scanf("%lld",&T);
  while(T--){
    int n,m;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=indec;i++){
      t[i]=edge();
    }
    indec=0;
    for(int i=1;i<=n;i++){
      e[i].clear();
    }
    for(int i=1;i<=m;i++){
      int x,y,z;
      scanf("%lld%lld%lld",&x,&y,&z);
      t[++indec]=edge(x,y,z);
      e[x].insert({y,indec});
      e[y].insert({x,indec});
    }
    solve(n);
  }
}

詳細信息

Test #1:

score: 0
Runtime Error

input:

100000
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
1...

output:


result: