oj.uz

Submission #854888

# Submission time Handle Problem Language Result Execution time Memory
854888 2023-09-29T09:27:16 Z khanhtai Wild Boar (JOI18_wild_boar) C++14
100 / 100
 5448 ms 692280 KB 
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "wildboar"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef pair<ii,ii> iv;
const int MAXN = 2103;
int plan[100005];
int n,m,q,l,u,v;
struct path{
    int s,e,w;
    path(int _s,int _e,int _w){
        s = _s;
        e = _e;
        w = _w;
    }
    path(){
        s = e = w = 0;
    }
};
int f(int x){return (((x-1)^1)+1);}

vector<int> g[MAXN];
vector<path> option[MAXN][MAXN];
vector<path> tmp,res;
int from[2*MAXN],to[2*MAXN],w[2*MAXN],dist[2*MAXN],cnt[2*MAXN];
bool visited[MAXN*2];
void eliminate(vector<path>&e){
    res.clear();
    res.shrink_to_fit();
    for(int times=1;times<=5;times++){
        path t = path(0,0,INF);
        for(auto p: e){
            int samestart=0,sameend=0,sameboth=0;
            for(auto cur: res){
                if (p.s == cur.s) samestart++;
                if (p.e == cur.e) sameend++;
                if (p.e == cur.e and p.s == cur.s) sameboth++;
            }
            if (samestart >= 2 or sameend >= 2 or sameboth>=1) continue;
            if (p.w < t.w) t=p;
        }
        res.pb(t);
    }
    e = res;
    e.shrink_to_fit();
}
vector<path> st[400005];
void unite(int node){
    st[node].clear();
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            if (st[node<<1][i].e != st[node<<1|1][j].s){
                st[node].pb(path(st[node<<1][i].s,st[node<<1|1][j].e, st[node<<1][i].w + st[node<<1|1][j].w));
            }
        }
    }
    eliminate(st[node]);
}
void build(int node,int l,int r){
    if (l+1==r){
       st[node] = option[plan[l]][plan[r]];
       return;
    }
    int mid = (l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid,r);
    unite(node);
}
void update(int node,int l,int r,int pos,int val){
    if (l+1==r and l==pos){
        plan[pos] = val;
        st[node] = option[plan[l]][plan[r]];
        return;
    }
    if (l+1==r and r==pos){
        plan[pos] = val;
        st[node] = option[plan[l]][plan[r]];
        return;
    }
    int mid = (l+r)>>1;
    if (pos <= mid) update(node<<1,l,mid,pos,val);
    if (pos >= mid) update(node<<1|1,mid,r,pos,val);
    unite(node);
}
main()
{
    fast;
   // freopen(TASKNAME".inp","r",stdin);
   // freopen(TASKNAME".out","w",stdout);
    cin>>n>>m>>q>>l;
    for(int i=1;i<=m;i++){
        cin>>from[i*2]>>to[i*2]>>w[2*i];
        from[i*2-1] = to[i*2];
        to[i*2-1] = from[i*2];
        w[2*i-1] = w[i*2];
        g[from[i*2]].pb(2*i);
        g[to[i*2]].pb(2*i-1);
    }
    for(int i=1;i<=n;i++ ){
        for(auto edgeid: g[i]){
            for(int j=1;j<=2*m;j++){
                dist[j] = INF;
                cnt[j]=0;
                visited[j]=false;
            }
            priority_queue<ii,vector<ii>,greater<ii>> pq;

            dist[edgeid] = w[edgeid];

            pq.push({dist[edgeid],edgeid});
            while(!pq.empty()){
                int curedge = pq.top().se;
                int du = pq.top().fi;
                int node = to[curedge];
//                cerr<<i<<' '<<du<<' '<<node<<' '<<curedge<<endl;

                pq.pop();

                if (visited[curedge] or cnt[node] >= 2) continue;
                visited[curedge] = true;
                cnt[node]++;

                for(auto nxtedge: g[node]){
                    if (nxtedge == f(curedge)) continue;
                    if (dist[nxtedge] > dist[curedge] + w[nxtedge]){
                        dist[nxtedge] = dist[curedge] + w[nxtedge];
                        pq.push({dist[nxtedge],nxtedge});
                    }
                }
            }
            for(int j=1;j<=2*m;j++){
                option[from[edgeid]][to[j]].pb(path(edgeid,f(j),dist[j]));
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            eliminate(option[i][j]);
//            for(auto x: option[i][j]){
////                cout<<x.s<<' '<<x.e<<' '<<x.w<<endl;
//            }
//            cout<<endl;
        }
    }
    for(int i=1;i<=l;i++){
        cin>>plan[i];
    }
    build(1,1,l);
    for(int i=1;i<=q;i++){
        int p,k;
        cin>>p>>k;
        update(1,1,l,p,k);
        int ans = INF;
        for(auto x: st[1]){
            ans = min(ans,x.w);
        }
        if (ans == INF) cout<<-1<<endl;
        else cout<<ans<<endl;
    }


}

Compilation message

wild_boar.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main()
      | ^~~~
wild_boar.cpp: In function 'int main()':
wild_boar.cpp:129:21: warning: unused variable 'du' [-Wunused-variable]
  129 |                 int du = pq.top().fi;
      |                     ^~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 113748 KB Output is correct
2 Correct 24 ms 113716 KB Output is correct
3 Correct 25 ms 113756 KB Output is correct
4 Correct 25 ms 113944 KB Output is correct
5 Correct 24 ms 113756 KB Output is correct
6 Correct 27 ms 113752 KB Output is correct
7 Correct 24 ms 113752 KB Output is correct
8 Correct 24 ms 113752 KB Output is correct
9 Correct 24 ms 113940 KB Output is correct
10 Correct 27 ms 113940 KB Output is correct
11 Correct 25 ms 113752 KB Output is correct
12 Correct 24 ms 113796 KB Output is correct
13 Correct 24 ms 113756 KB Output is correct
14 Correct 27 ms 113932 KB Output is correct
15 Correct 26 ms 113756 KB Output is correct
16 Correct 25 ms 113756 KB Output is correct
17 Correct 26 ms 113744 KB Output is correct
18 Correct 24 ms 113752 KB Output is correct
19 Correct 24 ms 113756 KB Output is correct
20 Correct 27 ms 114164 KB Output is correct
21 Correct 26 ms 113756 KB Output is correct
22 Correct 24 ms 113756 KB Output is correct
23 Correct 25 ms 113756 KB Output is correct
24 Correct 24 ms 113756 KB Output is correct
25 Correct 24 ms 113760 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 113748 KB Output is correct
2 Correct 24 ms 113716 KB Output is correct
3 Correct 25 ms 113756 KB Output is correct
4 Correct 25 ms 113944 KB Output is correct
5 Correct 24 ms 113756 KB Output is correct
6 Correct 27 ms 113752 KB Output is correct
7 Correct 24 ms 113752 KB Output is correct
8 Correct 24 ms 113752 KB Output is correct
9 Correct 24 ms 113940 KB Output is correct
10 Correct 27 ms 113940 KB Output is correct
11 Correct 25 ms 113752 KB Output is correct
12 Correct 24 ms 113796 KB Output is correct
13 Correct 24 ms 113756 KB Output is correct
14 Correct 27 ms 113932 KB Output is correct
15 Correct 26 ms 113756 KB Output is correct
16 Correct 25 ms 113756 KB Output is correct
17 Correct 26 ms 113744 KB Output is correct
18 Correct 24 ms 113752 KB Output is correct
19 Correct 24 ms 113756 KB Output is correct
20 Correct 27 ms 114164 KB Output is correct
21 Correct 26 ms 113756 KB Output is correct
22 Correct 24 ms 113756 KB Output is correct
23 Correct 25 ms 113756 KB Output is correct
24 Correct 24 ms 113756 KB Output is correct
25 Correct 24 ms 113760 KB Output is correct
26 Correct 25 ms 114012 KB Output is correct
27 Correct 99 ms 141520 KB Output is correct
28 Correct 92 ms 141392 KB Output is correct
29 Correct 209 ms 141136 KB Output is correct
30 Correct 211 ms 141580 KB Output is correct
31 Correct 187 ms 141160 KB Output is correct
32 Correct 194 ms 141172 KB Output is correct
33 Correct 218 ms 143052 KB Output is correct
34 Correct 221 ms 143012 KB Output is correct
35 Correct 193 ms 143116 KB Output is correct
36 Correct 202 ms 143064 KB Output is correct
37 Correct 216 ms 143160 KB Output is correct
38 Correct 221 ms 145748 KB Output is correct
39 Correct 206 ms 145488 KB Output is correct
40 Correct 215 ms 145752 KB Output is correct
41 Correct 214 ms 145752 KB Output is correct
42 Correct 212 ms 147208 KB Output is correct
43 Correct 211 ms 148836 KB Output is correct
44 Correct 218 ms 148692 KB Output is correct
45 Correct 167 ms 151632 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 113748 KB Output is correct
2 Correct 24 ms 113716 KB Output is correct
3 Correct 25 ms 113756 KB Output is correct
4 Correct 25 ms 113944 KB Output is correct
5 Correct 24 ms 113756 KB Output is correct
6 Correct 27 ms 113752 KB Output is correct
7 Correct 24 ms 113752 KB Output is correct
8 Correct 24 ms 113752 KB Output is correct
9 Correct 24 ms 113940 KB Output is correct
10 Correct 27 ms 113940 KB Output is correct
11 Correct 25 ms 113752 KB Output is correct
12 Correct 24 ms 113796 KB Output is correct
13 Correct 24 ms 113756 KB Output is correct
14 Correct 27 ms 113932 KB Output is correct
15 Correct 26 ms 113756 KB Output is correct
16 Correct 25 ms 113756 KB Output is correct
17 Correct 26 ms 113744 KB Output is correct
18 Correct 24 ms 113752 KB Output is correct
19 Correct 24 ms 113756 KB Output is correct
20 Correct 27 ms 114164 KB Output is correct
21 Correct 26 ms 113756 KB Output is correct
22 Correct 24 ms 113756 KB Output is correct
23 Correct 25 ms 113756 KB Output is correct
24 Correct 24 ms 113756 KB Output is correct
25 Correct 24 ms 113760 KB Output is correct
26 Correct 25 ms 114012 KB Output is correct
27 Correct 99 ms 141520 KB Output is correct
28 Correct 92 ms 141392 KB Output is correct
29 Correct 209 ms 141136 KB Output is correct
30 Correct 211 ms 141580 KB Output is correct
31 Correct 187 ms 141160 KB Output is correct
32 Correct 194 ms 141172 KB Output is correct
33 Correct 218 ms 143052 KB Output is correct
34 Correct 221 ms 143012 KB Output is correct
35 Correct 193 ms 143116 KB Output is correct
36 Correct 202 ms 143064 KB Output is correct
37 Correct 216 ms 143160 KB Output is correct
38 Correct 221 ms 145748 KB Output is correct
39 Correct 206 ms 145488 KB Output is correct
40 Correct 215 ms 145752 KB Output is correct
41 Correct 214 ms 145752 KB Output is correct
42 Correct 212 ms 147208 KB Output is correct
43 Correct 211 ms 148836 KB Output is correct
44 Correct 218 ms 148692 KB Output is correct
45 Correct 167 ms 151632 KB Output is correct
46 Correct 205 ms 146512 KB Output is correct
47 Correct 2778 ms 606400 KB Output is correct
48 Correct 2940 ms 613724 KB Output is correct
49 Correct 3085 ms 625344 KB Output is correct
50 Correct 3092 ms 609288 KB Output is correct
51 Correct 3036 ms 606700 KB Output is correct
52 Correct 3563 ms 644548 KB Output is correct
53 Correct 3578 ms 648732 KB Output is correct
54 Correct 3591 ms 641776 KB Output is correct
55 Correct 3597 ms 646660 KB Output is correct
56 Correct 3693 ms 645352 KB Output is correct
57 Correct 3783 ms 644424 KB Output is correct
58 Correct 3816 ms 644568 KB Output is correct
59 Correct 3839 ms 649856 KB Output is correct
60 Correct 3913 ms 643608 KB Output is correct
61 Correct 3982 ms 639540 KB Output is correct
62 Correct 3876 ms 623972 KB Output is correct
63 Correct 3804 ms 605252 KB Output is correct
64 Correct 2494 ms 691004 KB Output is correct
65 Correct 2473 ms 692232 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 113748 KB Output is correct
2 Correct 24 ms 113716 KB Output is correct
3 Correct 25 ms 113756 KB Output is correct
4 Correct 25 ms 113944 KB Output is correct
5 Correct 24 ms 113756 KB Output is correct
6 Correct 27 ms 113752 KB Output is correct
7 Correct 24 ms 113752 KB Output is correct
8 Correct 24 ms 113752 KB Output is correct
9 Correct 24 ms 113940 KB Output is correct
10 Correct 27 ms 113940 KB Output is correct
11 Correct 25 ms 113752 KB Output is correct
12 Correct 24 ms 113796 KB Output is correct
13 Correct 24 ms 113756 KB Output is correct
14 Correct 27 ms 113932 KB Output is correct
15 Correct 26 ms 113756 KB Output is correct
16 Correct 25 ms 113756 KB Output is correct
17 Correct 26 ms 113744 KB Output is correct
18 Correct 24 ms 113752 KB Output is correct
19 Correct 24 ms 113756 KB Output is correct
20 Correct 27 ms 114164 KB Output is correct
21 Correct 26 ms 113756 KB Output is correct
22 Correct 24 ms 113756 KB Output is correct
23 Correct 25 ms 113756 KB Output is correct
24 Correct 24 ms 113756 KB Output is correct
25 Correct 24 ms 113760 KB Output is correct
26 Correct 25 ms 114012 KB Output is correct
27 Correct 99 ms 141520 KB Output is correct
28 Correct 92 ms 141392 KB Output is correct
29 Correct 209 ms 141136 KB Output is correct
30 Correct 211 ms 141580 KB Output is correct
31 Correct 187 ms 141160 KB Output is correct
32 Correct 194 ms 141172 KB Output is correct
33 Correct 218 ms 143052 KB Output is correct
34 Correct 221 ms 143012 KB Output is correct
35 Correct 193 ms 143116 KB Output is correct
36 Correct 202 ms 143064 KB Output is correct
37 Correct 216 ms 143160 KB Output is correct
38 Correct 221 ms 145748 KB Output is correct
39 Correct 206 ms 145488 KB Output is correct
40 Correct 215 ms 145752 KB Output is correct
41 Correct 214 ms 145752 KB Output is correct
42 Correct 212 ms 147208 KB Output is correct
43 Correct 211 ms 148836 KB Output is correct
44 Correct 218 ms 148692 KB Output is correct
45 Correct 167 ms 151632 KB Output is correct
46 Correct 205 ms 146512 KB Output is correct
47 Correct 2778 ms 606400 KB Output is correct
48 Correct 2940 ms 613724 KB Output is correct
49 Correct 3085 ms 625344 KB Output is correct
50 Correct 3092 ms 609288 KB Output is correct
51 Correct 3036 ms 606700 KB Output is correct
52 Correct 3563 ms 644548 KB Output is correct
53 Correct 3578 ms 648732 KB Output is correct
54 Correct 3591 ms 641776 KB Output is correct
55 Correct 3597 ms 646660 KB Output is correct
56 Correct 3693 ms 645352 KB Output is correct
57 Correct 3783 ms 644424 KB Output is correct
58 Correct 3816 ms 644568 KB Output is correct
59 Correct 3839 ms 649856 KB Output is correct
60 Correct 3913 ms 643608 KB Output is correct
61 Correct 3982 ms 639540 KB Output is correct
62 Correct 3876 ms 623972 KB Output is correct
63 Correct 3804 ms 605252 KB Output is correct
64 Correct 2494 ms 691004 KB Output is correct
65 Correct 2473 ms 692232 KB Output is correct
66 Correct 155 ms 139876 KB Output is correct
67 Correct 809 ms 250756 KB Output is correct
68 Correct 2408 ms 660172 KB Output is correct
69 Correct 2634 ms 665984 KB Output is correct
70 Correct 2880 ms 685788 KB Output is correct
71 Correct 4403 ms 598988 KB Output is correct
72 Correct 4627 ms 607260 KB Output is correct
73 Correct 5145 ms 645992 KB Output is correct
74 Correct 5136 ms 649928 KB Output is correct
75 Correct 5171 ms 646536 KB Output is correct
76 Correct 4739 ms 622080 KB Output is correct
77 Correct 4656 ms 607900 KB Output is correct
78 Correct 4396 ms 603428 KB Output is correct
79 Correct 5337 ms 650052 KB Output is correct
80 Correct 5394 ms 649564 KB Output is correct
81 Correct 4974 ms 630728 KB Output is correct
82 Correct 5448 ms 649628 KB Output is correct
83 Correct 5205 ms 635260 KB Output is correct
84 Correct 5257 ms 610192 KB Output is correct
85 Correct 3683 ms 692280 KB Output is correct