Vijos 小胖的奇偶

第一遍做

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 using namespace std;

 int n,m;

 char ss[];

 int rela[];

 int fa[];

 int find(int x)

 {

     if(x==fa[x])return x;

     int ff=fa[x];

     fa[x]=find(ff);

     rela[x]=(rela[x]+rela[ff])%;

     return fa[x];

 }

 int main()

 {

     freopen("xp.in","r",stdin);

     freopen("xp.out","w",stdout);

     int i;

     int left,right;

     cin>>n>>m;

     int ans=m;

     for(i=;i<=n;i++)fa[i]=i;

     for(i=;i<=m;i++)

     {

         cin>>left>>right;

         scanf("%s",ss);

         left--;

         if(ss[]=='e')

         {

             int ffl=find(left);

             int ffr=find(right);

             if(ffl<ffr)

             {

                 fa[ffr]=ffl;

                 rela[ffr]=(rela[left]-rela[right]+)%;

             }

             else if(ffl>ffr)

             {

                 fa[ffl]=ffr;

                 rela[ffl]=(rela[right]-rela[left]+)%;

             }

             else

             {

                 if(rela[right]!=rela[left])

                 {

                     ans=i-;

                     break;

                 }

             }

         }

         if(ss[]=='o')

         {

             int ffl=find(left);

             int ffr=find(right);

             if(ffl<ffr)

             {

                 fa[ffr]=ffl;

                 rela[ffr]=(rela[left]-rela[right]+)%;

             }

             else if(ffl>ffr)

             {

                 fa[ffl]=ffr;

                 rela[ffl]=(rela[right]-rela[left]+)%;

             }

             else

             {

                 if(rela[right]==rela[left])

                 {

                     ans=i-;

                     break;

                 }

             }

         }

     }

     cout<<ans;

     return ;

 }

RE 80 注意长度范围QwQ

第二遍 map一下

 #include<iostream>

 #include<cstdlib>

 #include<cstdio>

 #include<cstring>

 #include<map>

 using namespace std;

 int n,m;

 char ss[];

 int rela[];

 int fa[];

 map<int,int>mp;

 int find(int x)

 {

     if(x==fa[x])return x;

     int ff=fa[x];

     fa[x]=find(ff);

     rela[x]=(rela[x]+rela[ff])%;

     return fa[x];

 }

 int main()

 {

     freopen("xp.in","r",stdin);

     freopen("xp.out","w",stdout);

     int i;

     int left,right;

     cin>>n>>m;

     int ans=m;

     int cnt=;

     for(i=;i<=;i++)

         fa[i]=i;

     for(i=;i<=m;i++)

     {

         cin>>left>>right;

         scanf("%s",ss);

         left--;

         if(mp[left]==){cnt++;mp[left]=cnt;}

         if(mp[right]==){cnt++;mp[right]=cnt;}

         if(ss[]=='e')

         {

             int ffl=find(mp[left]);

             int ffr=find(mp[right]);

             if(ffl<ffr)

             {

                 fa[ffr]=ffl;

                 rela[ffr]=(rela[mp[left]]-rela[mp[right]]+)%;

             }

             else if(ffl>ffr)

             {

                 fa[ffl]=ffr;

                 rela[ffl]=(rela[mp[right]]-rela[mp[left]]+)%;

             }

             else

             {

                 if(rela[mp[right]]!=rela[mp[left]])

                 {

                     ans=i-;

                     break;

                 }

             }

         }

         if(ss[]=='o')

         {

             int ffl=find(mp[left]);

             int ffr=find(mp[right]);

             if(ffl<ffr)

             {

                 fa[ffr]=ffl;

                 rela[ffr]=(rela[mp[left]]-rela[mp[right]]+)%;

             }

             else if(ffl>ffr)

             {

                 fa[ffl]=ffr;

                 rela[ffl]=(rela[mp[right]]-rela[mp[left]]+)%;

             }

             else

             {

                 if(rela[mp[right]]==rela[mp[left]])

                 {

                     ans=i-;

                     break;

                 }

             }

         }

     }

     cout<<ans;

     return ;

 }

AC啦啦啦

2019.3.23