답안 #899259

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
899259 2024-01-05T16:25:03 Z Ludissey Training (IOI07_training) C++14
20 / 100
300 ms 524288 KB
#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
int n,m;
const int LOG=11;
#define LSOne(S) (S & (-S))
vector<vector<int>> paved;
vector<vector<int>> child;
vector<vector<int>> indN;
vector<vector<pair<int,int>>> memo2;
vector<int> depth;
vector<vector<int>> parent;
vector<vector<pair<pair<int,int>,int>>> edges;
vector<vector<int>> memo;
vector<int> maskCalc;

int lca(int a, int b){
    if(depth[b]>depth[a]) swap(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 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 parent[a][0];
}
 
int dp(int x, int mask, int prev){
    if(memo[x][mask]!=-1) return memo[x][mask];
    if(child[x].size()==0) return memo[x][mask]=0;
    int mx=0;
    if(__builtin_popcount(mask)>=child[x].size()) return memo[x][mask]=0;
    if(prev==-1){
        if(maskCalc[x]==-1){
            for (int i = 0; i < child[x].size(); i++)
            {
                if((mask&(1<<i))!=0) continue;
                mx+=dp(child[x][i],0,-1);
            }
            maskCalc[x]=mx;
        }else{
            int dfMask=mask;
            mx=maskCalc[x];
            while(dfMask>0) {
                int ls=LSOne(dfMask);
                mx-=dp(child[x][ls-1],0,-1);
                dfMask-=(1<<(ls-1));
            }
        }
    }
    prev=mx;
    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;
        if(memo2[a][b].first==-1){
            int ap=a;
            int bp=b;
            int sum=0;
            while((parent[ap][0]!=x&&ap!=x)||(parent[bp][0]!=x&&bp!=x)){
                if((parent[ap][0]!=x&&ap!=x)){
                    int bitmaskA=(1<<indN[parent[ap][0]][ap]);
                    sum+=dp(parent[ap][0],bitmaskA,-1);
                    ap=parent[ap][0];
                }
                if((parent[bp][0]!=x&&bp!=x)){
                    int bitmaskB=(1<<indN[parent[bp][0]][bp]);

                    sum+=dp(parent[bp][0],bitmaskB,-1);
                    bp=parent[bp][0];
                }
            }
            int bitmask=0;
            if(a!=x) {
                sum+=dp(a,0,-1);
                bitmask+=(1<<indN[x][ap]);
            }
            if(b!=x) {
                sum+=dp(b,0,-1);
                bitmask+=(1<<indN[x][bp]);
            }
            memo2[a][b]={sum,bitmask};
        }
        if((memo2[a][b].second&mask)!=0) continue;
        int new_prev=prev;
        if(a!=x) new_prev-=dp(a,0,-1);
        if(b!=x) new_prev-=dp(b,0,-1);
        mx=max(mx,memo2[a][b].first+c+dp(x,memo2[a][b].second,new_prev));
    }
    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);
    maskCalc.resize(n+1,-1);
    parent.resize(n+1, vector<int>(LOG, 0));
    indN.resize(n+1, vector<int>(n+1, -1));
    memo2.resize(n+1, vector<pair<int,int>>(n+1,{-1,-1}));
    memo.resize(n+1, vector<int>(pow(2,10)+2,-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);
            indN[x][u]=child[x].size();
            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 lc=lca(a,b);
        int d=(depth[a]+depth[b])-2*depth[lc];
        if(d%2!=0) continue;
        edges[lc].push_back({{a,b},c});
    }
    
    cout << sum-dp(1,0,-1) << "\n";
    return 0;
}
 

Compilation message

training.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
training.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
training.cpp: In function 'int dp(int, int, int)':
training.cpp:41:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             for (int i = 0; i < child[x].size(); i++)
      |                             ~~^~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 458 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 16740 KB Output is correct
2 Correct 19 ms 16740 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 348 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 349 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 326 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 342 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 335 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 365 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 333 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 354 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -