Submission #445576

#	Time	Username	Problem	Language	Result	Execution time	Memory
445576		hgmhc	Putovanje (COCI20_putovanje)	C++17	0 / 110	53 ms	10488 KiB

putovanje

#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define PER(i,a,b) for (auto i = (b); i >= (a); --i)
#define log2(x) (31-__builtin_clz(x))
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define SZ(x) (int)(x).size()
#define PB push_back
#define FI first
#define SE second
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define debug(x) cout << #x << " is " << x << el
#define el '\n'
using namespace std; using ll = long long; using ii = pair<int,int>; using iii = tuple<int,int,int>;
void solution(); int main() {ios::sync_with_stdio(0); cin.tie(0); solution();}
const int N = 200003;
vector<int> adj[N];
vector<iii> edge;
int n, ans;
bool chk[N];
 
int dfs(int s, int e) {
    chk[s] = true;
    int sz = 1;
    for (auto u : adj[s]) if (u != e) {
        sz += dfs(u,s);
    }
    return sz;
}
 
void input() {
    cin >> n;
    REP(i,1,n-1) {
        int a, b, p, q;
        cin >> a >> b >> p >> q;
        ans += p;
        edge.push_back({q-p,a,b});
        adj[a].push_back(b); adj[b].push_back(a);
    }
}
void solution() {
    input();
    if (n <= 2000) {
        for (auto [w,a,b] : edge) {
            fill(chk,chk+n+1,0);
            int sz = dfs(a,b);
            bool wow = true;
            REP(i,1,sz) if (!chk[i]) wow = false;
            if (wow) continue;
            REP(i,n-sz+1,n) if (!chk[i]) wow = false;
            if (!wow) ans += w;
        }
        cout << ans;
    } else {
        int cnt = 0;
        if (adj[1].size() == 1) {
            REP(i,2,n) {
                if (adj[i-1][0] == i || adj[i-1][1] == i) {
                    ++cnt;
                } else break;
            }
        }
        if (adj[n].size() == 1) {
            PER(i,1,n-1) {
                if (adj[i+1][0] == i || adj[i+1][1] == i) {
                    ++cnt;
                } else break;
            }
        }
        cout << cnt;
    }
}

• Subtask 1: 0 / 20
• Subtask 2: 0 / 25
• Subtask 3: 0 / 65