oj.uz

답안 #973446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973446 2024-05-02T02:37:19 Z modwwe Putovanje (COCI20_putovanje) C++17
110 / 110
 107 ms 50256 KB 
#include<bits/stdc++.h>
#define int long long
#define d0 1
#define d1 11
#define d2 110
#define d3 1010
#define d4 10010
#define d5 100010
#define d6 1000010
#define down cout<<'\n';
#define NHP     ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0);
#define modwwe  int t;cin>>t; while(t--)
#define debug(x) cerr<<x<<" ";
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define sz(s) s.size()
#define pii pair<int,int>
#define pb push_back
#define checktime   cout << (double)clock() / CLOCKS_PER_SEC * 1000  << " ms";
#define rep(i,m,n) for(int i=m;i<=n;i++)
#define reb(i,m,n) for(int i=m;i>=n;i--)
#define ALL(v) v.begin(), v.end()
#define base 31
#define base2 37
using namespace std;
void phongbeo();
void de();
template<typename A, typename B>istream& operator>>(istream& in, pair<A, B> &v)
{
    in >> v.first >> v.second;
    return in;
}
template<typename A, typename B> ostream& operator<<(ostream& out, const pair<A, B> &v)
{
    out << v.first << " " << v.second << " ";
    return out;
}
template < class T > bool minimize(T& a, const T& b)
{
    return b < a ? a = b, 1 : 0;
}
template < class T > bool maximize(T& a, const T& b)
{
    return a < b ? a = b, 1 : 0;
}
mt19937 rd(chrono::high_resolution_clock::now().time_since_epoch().count    ());
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int dx2[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dy2[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const int mod2=1e9+7;
const int mod=20215201314;
const int  mod1=998244353;
struct ib
{
    int a;
    int b;
};
struct icd
{
    int a,b;
};
struct ic
{
    int a,b,c;
};
struct id
{
    int a,b,c,d;
};
int minn=1e9,maxx=-1e9;
int n,m,s2,s4,s3,sf,k,l,r,dem=0,mid,s5,s6,mx,s7,s8,s9,mx2,res,dem2=0;
int  s,i;
int el=29;
main()
{
#ifndef ONLINE_JUDGE
    //fin(task),fou(task);
#endif
    NHP
//modwwe
    phongbeo(),down
#ifndef ONLINE_JUDGE
    //checktime
#endif
}
vector<ic> v[2*d5];
int st[18][2*d5],depth[2*d5],dp[2*d5];
void dfs(int x,int y)
{st[0][x]=y;
depth[x]=depth[y]+1;
     for(auto f:v[x])
     { if(f.a!=y)
          dfs(f.a,x);
     }
}
void lca(int x,int y)
{
     if(depth[x]>depth[y]) swap(x,y);
     int sx= depth[y]-depth[x];
     for(int j=0;j<18;j++)
 if(bit(sx,j))
y=st[j][y];
if(x==y){dp[x]-=2;
 return;
 }
 for(int j=17;j>=0;--j)
     if(st[j][x]!=st[j][y])
 {
      y=st[j][y];
       x=st[j][x];
 }
  dp[st[0][x]]-=2;
 }
 void dfs2(int x,int y)
 {
     for(auto f:v[x])
     {
          if(f.a!=y)
          {
              dfs2(f.a,x);
s6+=min(f.b*dp[f.a],f.c);
                dp[x]+=dp[f.a];
          }
     }
 }
    void phongbeo()
{
    cin>>n;
 for(int i=1;i<n;i++)
 {
     cin>>s2>>s3>>s4>>s5;
      v[s2].pb({s3,s4,s5});
      v[s3].pb({s2,s4,s5});
 }
 dfs(1,0);
 for(int j=1;j<18;j++)
    for(int i=1;i<=n;i++)
    st[j][i]=st[j-1][st[j-1][i]];
 for(int i=1;i<=n-1;i++)
 {
    dp[i]++;
    dp[i+1]++;
    lca(i,i+1);
 }
 dfs2(1,0);
 cout<<s6;
    }

Compilation message

putovanje.cpp:78:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   78 | main()
      | ^~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 34140 KB Output is correct
2 Correct 6 ms 34396 KB Output is correct
3 Correct 6 ms 34392 KB Output is correct
4 Correct 6 ms 34272 KB Output is correct
5 Correct 6 ms 34396 KB Output is correct
6 Correct 5 ms 34136 KB Output is correct
7 Correct 5 ms 34136 KB Output is correct
8 Correct 6 ms 34140 KB Output is correct
9 Correct 6 ms 34396 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 69 ms 47188 KB Output is correct
2 Correct 70 ms 48448 KB Output is correct
3 Correct 82 ms 50256 KB Output is correct
4 Correct 87 ms 49492 KB Output is correct
5 Correct 5 ms 34136 KB Output is correct
6 Correct 72 ms 46888 KB Output is correct
7 Correct 43 ms 43604 KB Output is correct
8 Correct 72 ms 47112 KB Output is correct
9 Correct 45 ms 47256 KB Output is correct
10 Correct 46 ms 46928 KB Output is correct
11 Correct 48 ms 48052 KB Output is correct
12 Correct 49 ms 48208 KB Output is correct

Subtask #3
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 34140 KB Output is correct
2 Correct 6 ms 34396 KB Output is correct
3 Correct 6 ms 34392 KB Output is correct
4 Correct 6 ms 34272 KB Output is correct
5 Correct 6 ms 34396 KB Output is correct
6 Correct 5 ms 34136 KB Output is correct
7 Correct 5 ms 34136 KB Output is correct
8 Correct 6 ms 34140 KB Output is correct
9 Correct 6 ms 34396 KB Output is correct
10 Correct 69 ms 47188 KB Output is correct
11 Correct 70 ms 48448 KB Output is correct
12 Correct 82 ms 50256 KB Output is correct
13 Correct 87 ms 49492 KB Output is correct
14 Correct 5 ms 34136 KB Output is correct
15 Correct 72 ms 46888 KB Output is correct
16 Correct 43 ms 43604 KB Output is correct
17 Correct 72 ms 47112 KB Output is correct
18 Correct 45 ms 47256 KB Output is correct
19 Correct 46 ms 46928 KB Output is correct
20 Correct 48 ms 48052 KB Output is correct
21 Correct 49 ms 48208 KB Output is correct
22 Correct 107 ms 43828 KB Output is correct
23 Correct 78 ms 42832 KB Output is correct
24 Correct 92 ms 43600 KB Output is correct
25 Correct 5 ms 34136 KB Output is correct
26 Correct 55 ms 38520 KB Output is correct
27 Correct 74 ms 42536 KB Output is correct
28 Correct 42 ms 45736 KB Output is correct
29 Correct 51 ms 48312 KB Output is correct
30 Correct 62 ms 47952 KB Output is correct
31 Correct 6 ms 34392 KB Output is correct