제출 #1165236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165236		salmon	Janjetina (COCI21_janjetina)	C++20	0 / 110	1 ms	2632 KiB

Main

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

int N,K;
bool visited[100100];
vector<vector<pair<int,int>>> v;
vector<pair<int,int>> adjlst[100100];
int u,v1,w;
int sise[100100];
int ft[100100];
int parent[100100];

int query(int i){
	i++;
	int v = 0;
	while(i != 0){
		v += ft[i];
		i -= (i&(-i));
	}
	return v;
}

void update(int i, int N){
	i++;
	N++;
	while(i <= N){
		ft[i]++;
		i += (i&(-i));
	}
}

void dfs(int i, int p){
    sise[i] = 1;
    parent[i] = p;

    for(pair<int,int> ii : adjlst[i]){
        if(visited[ii.first] || ii.first == p) continue;
        dfs(ii.first,i);
        sise[i] += sise[ii.first];
    }
}

void digfs(int i, int p, int vi, int de, int it){
	v[it].push_back({vi,de});

    for(pair<int,int> ii : adjlst[i]){
        if(visited[ii.first] || ii.first == p) continue;
        digfs(ii.first,i,max(ii.second,vi),de+1,it);
    }
}

long long decomp(int i){
    dfs(i,-1);

    int n = sise[i];
    int c = i;

    while(true){
        int temp = c;
        for(pair<int,int> ii : adjlst[c]){
            if(visited[ii.first] || ii.first == parent[c]) continue;
            if(sise[ii.first] >= n/2){
                c = ii.first;
                break;
            }
        }
        if(temp == c) break;
    }
    
    vector<pair<int,int>> vt;

    int cont = 0;
    long long int ans = 0;
    for(pair<int,int> ii : adjlst[c]){
        if(visited[ii.first]) continue;
        v.push_back({});
        digfs(ii.first,c,ii.second,1,cont);
        sort(v[cont].begin(),v[cont].end());
        cont++;
        
		int m = 0;
		
		for(pair<int,int> ii : v[cont - 1]){
			m = max(m,ii.second);
		}
		
		for(pair<int,int> ii : v[cont - 1]){
			if(ii.first -ii.second >= 0) ans -= query(ii.first - ii.second);
			update(ii.second,m);

			vt.push_back(ii);
		}
		
		for(int i = 0; i <= m; i++) ft[i] = 0;
    }

    sort(vt.begin(),vt.end());

	int m = 0;
		
	for(pair<int,int> ii : vt){
		m = max(m,ii.second);
	}

	update(0,m);

	for(pair<int,int> ii : vt){
		if(ii.first -ii.second >= 0) ans += query(ii.first - ii.second);
		update(ii.second,m);
	}
	
	for(int i = 0; i <= m; i++) ft[i] = 0;
	
	v.clear();
	
	visited[c] = true;
	
	for(pair<int,int> ii : adjlst[c]){
		if(visited[ii.first]) continue;
		ans += decomp(ii.first);
	}
	
	return ans;
}

int main(){

    scanf(" %d",&N);
    scanf(" %d",&K);

    for(int i = 0; i < N - 1; i++){
        scanf(" %d",&u);
        scanf(" %d",&v1);
        scanf(" %d",&w);
        w -= K;
        adjlst[u].push_back({v1,w});
        adjlst[v1].push_back({u,w});
    }

    for(int i = 1; i <= N; i++) visited[i] = false;

    printf("%lld",decomp(1) * 2);
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:128:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:129:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
Main.cpp:132:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  132 |         scanf(" %d",&u);
      |         ~~~~~^~~~~~~~~~
Main.cpp:133:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |         scanf(" %d",&v1);
      |         ~~~~~^~~~~~~~~~~
Main.cpp:134:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |         scanf(" %d",&w);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 60