Submission #896312

#	Time	Username	Problem	Language	Result	Execution time	Memory
896312		Ludissey	Training (IOI07_training)	C++14	20 / 100	1092 ms	524288 KiB

training

#include <bits/stdc++.h>
using namespace std;

#define int long long
int n,m;
const int LOG=31;

vector<vector<int>> paved;
vector<vector<int>> child;
vector<int> depth;
vector<vector<int>> parent;
vector<vector<pair<pair<int,int>,int>>> edges;
map<pair<int,int>, int> memo;

vector<vector<int>> memoLCA;

int lca(int a, int b){
    if(depth[b]>depth[a]) swap(a,b);
    int _a=a;
    int _b=b;
    if(memoLCA[a][b]!=-1) return memoLCA[_a][_b];
    int k=depth[a]-depth[b];
    for (int j = LOG-1; j >= 0; j--) if(k&(1<<j)) a=parent[a][j];
    if(a==b) return memoLCA[_a][_b]=a;
    for (int j = LOG-1; j >= 0; j--)
    {
        if(parent[a][j]!=parent[b][j]) {
            a=parent[a][j];
            b=parent[b][j];
        }
    }
    return memoLCA[_a][_b]=parent[a][0];
}

int dp(int x, int mask){
    if(memo.find({x,mask})!=memo.end()) return memo[{x,mask}];
    if(child[x].size()==0) return memo[{x,mask}]=0;
    int mx=0;
    for (int i = 0; i < child[x].size(); i++)
    {
        if((mask&(1<<i))!=0) continue;
        mx+=dp(child[x][i],0);
    }
    for(auto u : edges[x]) {
        int a=u.first.first;
        int b=u.first.second;
        int c=u.second;
        int d=(depth[a]+depth[b])-2*depth[x];
        if(d%2!=0) continue;
        int sum=0;
        int ap=a;
        int bp=b;
        while(parent[ap][0]!=x&&ap!=x){
            int bitmask=0;
            for (int j = 0; j < child[parent[ap][0]].size(); j++)
            {
                if(child[parent[ap][0]][j]==ap) { bitmask+=(1<<j); break; }
            }
            sum+=dp(parent[ap][0],bitmask);
            ap=parent[ap][0];
        }
        while(parent[bp][0]!=x&&bp!=x){
            int bitmask=0;
            for (int j = 0; j < child[parent[bp][0]].size(); j++)
            {
                if(child[parent[bp][0]][j]==bp) { bitmask+=(1<<j); break; }
            }
            sum+=dp(parent[bp][0],bitmask);
            bp=parent[bp][0];
        }
        if(a!=x) sum+=dp(a,0);
        if(b!=x) sum+=dp(b,0);
        int bitmask=0;
        bool br=false;
        for (int j = 0; j < child[x].size(); j++)
        {
            if(child[x][j]==ap||child[x][j]==bp) { 
                if((mask&(1<<j))!=0) br=true;
                bitmask+=(1<<j); 
            }
        }
        if(br) continue;
        sum+=dp(x,bitmask);
        mx=max(mx,sum+c);
    }
    return memo[{x,mask}]=mx;
}

signed main() {
	// Input:
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin>>n>>m;
    paved.resize(n+1);
    depth.resize(n+1);
    parent.resize(n+1, vector<int>(LOG, 0));
    memoLCA.resize(n+1, vector<int>(n+1, -1));
    edges.resize(n+1);
    child.resize(n+1);
    int sum=0;
    vector<pair<pair<int,int>, int>> edgesTOPROCESS;
    for (int i = 0; i < m; i++)
    {
        int a,b,c; cin >> a >> b >> c;
        sum+=c;
        if(a>b) swap(a,b);
        if(c==0) {
            paved[a].push_back(b);
            paved[b].push_back(a);
        }
        else {
            edgesTOPROCESS.push_back({{a,b},c});
        }
    }
    queue<int> q;
    q.push(1);
    parent[1][0]=1;
    depth[1]=0;
    vector<bool> visited(n+1);
    while(!q.empty()){
        int x=q.front(); q.pop();
        visited[x]=true;
        for (auto u: paved[x])
        {
            if(visited[u]) continue;
            q.push(u);
            child[x].push_back(u);
            parent[u][0]=x;
            depth[u]=depth[x]+1;
        }
        
    }
    for (int j = 1; j < LOG; j++) for (int i = 1; i <= n; i++) parent[i][j]=parent[parent[i][j-1]][j-1];


    for (int i = 0; i < m-(n-1); i++)
    {
        int a=edgesTOPROCESS[i].first.first;
        int b=edgesTOPROCESS[i].first.second;
        int c=edgesTOPROCESS[i].second;
        int d=(depth[a]+depth[b])-2*depth[lca(a,b)];
        if(d%2!=0) continue;
        edges[lca(a,b)].push_back({{a,b},c});
    }
    
    cout << sum-dp(1,0) << "\n";
    return 0;
}

Compilation message (stderr)

training.cpp: In function 'long long int dp(long long int, long long int)':
training.cpp:39:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < child[x].size(); i++)
      |                     ~~^~~~~~~~~~~~~~~~~
training.cpp:55:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for (int j = 0; j < child[parent[ap][0]].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:64:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for (int j = 0; j < child[parent[bp][0]].size(); j++)
      |                             ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
training.cpp:75:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for (int j = 0; j < child[x].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 0 / 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