Submission #1132348

#	Time	Username	Problem	Language	Result	Execution time	Memory
1132348		Ak_16	Training (IOI07_training)	C++20	30 / 100	2 ms	840 KiB

training

#include <iostream>
#include <vector>
#include <utility>

using namespace std;

int pos[5000];
int pla[5000];
int cur;
int vis[5000];

    int n,m;
    
    vector<int> adj1[5000];
    vector<pair<int, int>> adj2[5000];
    
    int dp[5000];
    int cnt[5000];

void dfs1(int no){
  vis[no]=1;
  pos[no] = cur;
  pla[cur] = no;
  cur++;
  for(auto x : adj1[no]){
    if(vis[x]==0){
      dfs1(x);
    }
  }
}

int main() 
{
  cin>>n>>m;
    cur=1;
    dp[0] = 0;
    for(int i=0; i<=4000; i++){cnt[i]=0; vis[i]=0;}
    int cost = 0;
    
     
    
    int u,v,w;
    
    for(int i=1; i<=m; i++){
      cin>>u>>v>>w;
      cost += w;
      if(w==0){adj1[u].push_back(v); adj1[v].push_back(u); cnt[u]++; cnt[v]++;}
      else {
        adj2[u].emplace_back(v, w);
        adj2[v].emplace_back(u, w);
      }
    }
    for(int i=1; i<=n; i++){
      if(cnt[i]==1){ dfs1(i); break;}
    }
    for(int i=1; i<=n; i++){
      dp[i] = dp[i-1];
      for(auto edge : adj2[pla[i]]){
        if(pos[edge.first] < i && (i + pos[edge.first]) %2 == 0){
          dp[i] = max(dp[i], edge.second + dp[pos[edge.first]]);
        }
      }
    }
    cout<<cost-dp[n]<<endl;
    
    
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9