Submission #1316773

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316773		athena	Grapevine (NOI22_grapevine)	C++20	0 / 100	3094 ms	12436 KiB

Main

#include <bits/stdc++.h>
using namespace std;
void bfs(vector<vector<pair<int,int>>>&adj,int n,int s,vector<int>&dis,vector<bool>&vis,vector<int>&p,vector<vector<int>>&c)
{
    queue<pair<int,int>>q;
    q.push({s,0});
    while(!q.empty())
    {
        auto [y,w]=q.front();q.pop();
        vis[y]=1;
        for(auto [u,v]:adj[y])
        {
            if(!vis[u])
            {
                p[u]=y;
                c[y].push_back(u);
                dis[u]=dis[y]+v;
                q.push({u,v});
            }
        }
    }
}
int main(){
    int n,q;
    cin>>n>>q;
    vector<vector<pair<int,int>>>adj(n+1);
    for(int i=0;i<n-1;i++)
    {
        int x,y,w;
        cin>>x>>y>>w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    vector<int>dis(n+1);
    vector<bool>vis(n+1,false);
    vector<int>p(n+1);
    vector<int>gpe(n+1,0);
    vector<vector<int>>c(n+1);
    bfs(adj,n,1,dis,vis,p,c);
   // for(int i=1;i<=n;i++)
   // cout<<dis[i]<<" ";
   // cout<<endl;
  //  for(int i=1;i<=n;i++)
  // cout<<c[i]<<" ";
   while(q--)
   {
       int t;
       cin>>t;
       if(t==1)//seek
       {int s;
       cin>>s;
           int ans=1e18;
           for(int i=1;i<=n;i++)
           {
               if(gpe[i]==1)
               {
                   ans=min(ans,dis[i]);
               }
           }
           cout<<ans<<endl;
       }
       if(t==2)
       {
           int x;
           cin>>x;
           if(gpe[x]==1)
           gpe[x]=0;
           else
           gpe[x]=1;
       }
       if(t==3)
       {
           int x,y,w;
           cin>>x>>y>>w;
           if(p[x]==y)//y parent
           {int z=x;
           int pp=y;
                queue<int>q;
             q.push(x);
             int old=dis[x];
             dis[x]=dis[y]+w;
             
             while(!q.empty())
             {
                 int v=q.front();q.pop();
                 for(int u:c[v])
                 {
                    if(u!=v)
                    {
                        dis[u]=dis[u]-old+w;
                        q.push(u);
                    }
                 }
             }
             //   cout<<"NEWW "<<endl;
           // for(int i=1;i<=n;i++)
          //  cout<<dis[i]<<" ";
           /// cout<<endl;
           }
           else//x parent
           {int z=y;
           //change for all children of y
           int old=dis[y];//6
           int sub=dis[y]-dis[x];//4
             dis[y]=dis[x]+w;//2
             queue<int>q;
             q.push(y);
             //dis[y]=(dis[y]-dis[x])+w;
             while(!q.empty())
             {
                 int v=q.front();q.pop();
                 for(int u:c[v])
                 {//cout<<"U "<<u<<endl;
                    if(u!=v)
                    {
                          //cout<<"DIS U"<<dis[u]-sub<<endl;
                        dis[u]=dis[u]-sub+w;
                       // cout<<"DIS U"<<dis[u]<<endl;
                        q.push(u);
                    }
                 }
             }
            // cout<<"NEW "<<endl;
            //  for(int i=1;i<=n;i++)
            //cout<<dis[i]<<" ";
           // cout<<endl;
           }
       }
   }
    
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:52:20: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   52 |            int ans=1e18;
      |                    ^~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 15
• Subtask 5: 0 / 18
• Subtask 6: 0 / 32