Submission #593240

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
593240	2022-07-10 15:52:00	chirathnirodha	경주 (Race) (IOI11_race)	C++17	100 / 100	2775 ms	80780 KiB

race

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
#include "race.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first
#define S second 
#define P push
#define I insert
typedef long long ll;
const ll INF=10000000000000;
const int maxn=200000;
ll n,k;
int ans=INT32_MAX;
vector<pair<ll,ll> > v[maxn];
int parent[maxn];
int subsiz[maxn];
int len[maxn];
ll dist[maxn];
int dfs(int x,set<int> s){
  subsiz[x]=1;
  for(int i=0;i<v[x].size();i++){
    int y=v[x][i].F;
    if(parent[x]==y || s.count(y))continue;
    parent[y]=x;
    dist[y]=dist[x]+v[x][i].S;
    len[y]=len[x]+1;
    subsiz[x]+=dfs(y,s);
  }
  return subsiz[x];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

race.cpp: In function 'int dfs(int, std::set<int>)':
race.cpp:22:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |   for(int i=0;i<v[x].size();i++){
      |               ~^~~~~~~~~~~~
race.cpp: In function 'int find_centroid(int, int, std::set<int>, int)':
race.cpp:34:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(int i=0;i<v[x].size();i++){
      |               ~^~~~~~~~~~~~
race.cpp: In function 'std::map<long long int, int> func(int, int, std::set<int>)':
race.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |   for(int i=0;i<v[cen].size();i++){
      |               ~^~~~~~~~~~~~~~
race.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<v[c].size();i++){
      |                 ~^~~~~~~~~~~~
race.cpp:87:22: warning: 'cenparlen' may be used uninitialized in this function [-Wmaybe-uninitialized]
   87 |     if(mp.count(k-p.F-disty)==0)continue;
      |                 ~~~~~^~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57