QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#326018#6315. 填数游戏littlecatCompile Error//C++146.8kb2024-02-12 07:42:072024-02-12 07:42:08

Judging History

你现在查看的是最新测评结果

  • [2024-02-12 07:42:08]
  • 评测
查看
  • [2024-02-12 07:42:07]
  • 提交

answer

// #define DEBUG
int TIMER=20;
#define TIME if(!TIMER--)exit(0);
#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
using namespace std; const int mx=1000000; typedef pair<int,int> pi;
#define pb push_back
#define f first
#define s second

pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
pi e[mx],es[mx]; vector<int> adj[mx]; //graph

int cntE,cntV; bool vis[mx]; //components
void dfs1(int c)
{
    if(vis[c]) return; cntV++, cntE+=adj[c].size(), vis[c]=1;
    for(int t:adj[c]) dfs1(e[t].f+e[t].s-c);
}

bool cycle[mx],cycledone; int cpar[mx],rt;
void dfs2(int c, int p)
{
    for(int t:adj[c]) if(t!=p)
    {
        int k=e[t].f+e[t].s-c; if(cpar[k]==-1) cpar[k]=c, dfs2(k,t); else if(!cycledone)
        {rt=c,cycledone=1; while(1) {cycle[rt]=1; if(rt==k) break; rt=cpar[rt];}}
    }
}
bool vis3[mx]; int cnt3;
void dfs3(int c, int p)
{
    if(vis3[c]) return; vis3[c]=1; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c; if(k==p) continue; dfs3(k,c);
        if(!cycle[k]) cnt3+=k==es[t].f||k==es[t].s;
    }
}
vector<int> cv, cn;
void getcycle(int c)
{
    cn.pb(c); if(c==rt&&!cv.empty()) return; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c;
        if(cycle[k]&&!(!cv.empty()&&t==cv.back())) {cv.pb(t), getcycle(k); break;}
    }
}

int solve()
{
#ifdef DEBUG
cout<<"Start\n"<<flush;
#endif
    //note: swap m/n
    int m,n,ans=0; cin>>m>>n;
    for(int i=0; i<n; i++) adj0[i].clear(),adj[i].clear(), vis[i]=vis3[i]=0, cycle[i]=0, cpar[i]=-1;
    for(int i=0; i<m; i++) edge[i]=1;
    //input and delete |T|=1
{
    int a,b;
    for(int i=0; i<m; i++) {int c; cin>>c>>a; if(c==2) cin>>b; else b=0; s1[i]=pi(a-1,b-1);}
    for(int i=0; i<m; i++) {int c; cin>>c>>a; if(c==2) cin>>b; else b=0; s2[i]=pi(a-1,b-1);
        sz1[i]=2-c, adj0[a-1].pb(i); if(c==2) adj0[b-1].pb(i);}
    vector<int> rm; for(int i=0; i<m; i++) if(sz1[i]) rm.pb(i);
    while(!rm.empty())
    {
        int i=rm.back(); rm.pop_back(); if(!edge[i]) continue; if(s2[i].f==-1) return -1;
        ans+=s2[i].f==s1[i].f||s2[i].f==s1[i].s, edge[i]=0;
#ifdef DEBUG
cout<<"Assign "<<i<<' '<<s2[i].f<<" ("<<s2[i].s<<")\n";
#endif
        for(int j:adj0[s2[i].f]) {if(s2[j].f==s2[i].f) s2[j].f=s2[j].s; s2[j].s=-1, rm.pb(j);}
    }
    int E=0;
    for(int i=0; i<m; i++) if(edge[i]) adj[s2[i].f].pb(E),adj[s2[i].s].pb(E), e[E]=s2[i],es[E++]=s1[i];
    m=E;
}
#ifdef DEBUG
cout<<m<<' '<<ans<<'\n'; for(int i=0; i<m; i++) cout<<e[i].f<<' '<<e[i].s<<' '<<es[i].f<<' '<<es[i].s<<'\n';
for(int i=0; i<n; i++) {cout<<i<<'\t'; for(int t:adj[i]) cout<<t<<' '; cout<<'\n';} cout<<flush;
#endif
for(int i=0; i<n; i++) if(!vis[i])
{
    //count edges
    cntE=cntV=0, dfs1(i); if(cntE>2*cntV) return -1;
    if(cntE==2*cntV)
    {
        //cycle with trees: explicit formul
        cycledone=0, dfs2(i,-1);
        cnt3=0, dfs3(rt,-1), ans+=cnt3;
        cv.clear(),cn.clear(), getcycle(rt);
        int A=0,B=0,C=0; for(int j=0; j<cv.size(); j++)
        {
            bool x1=cn[j]==es[cv[j]].f||cn[j]==es[cv[j]].s, x2=cn[j+1]==es[cv[j]].f||cn[j+1]==es[cv[j]].s;
            if(x1&&x2) C++; else if(x1) A++; else if(x2) B++;
        }
        ans+=min(min(A,B)+C,(A+B+C)/2);
    }
    else
    {
        //tree with variable root: dp
        ;
    }
}
    return ans;
}
int main()
{
    int T; cin.sync_with_stdio(0),cin.tie(0),cin>>T; while(T--) cout<<solve()<<'\n';
}// #define DEBUG
int TIMER=20;
#define TIME if(!TIMER--)exit(0);
#pragma GCC optimize("O3")
#include <iostream>
#include <vector>
using namespace std; const int mx=1000000; typedef pair<int,int> pi;
#define pb push_back
#define f first
#define s second

pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
pi e[mx],es[mx]; vector<int> adj[mx]; //graph

int cntE,cntV; bool vis[mx]; //components
void dfs1(int c)
{
    if(vis[c]) return; cntV++, cntE+=adj[c].size(), vis[c]=1;
    for(int t:adj[c]) dfs1(e[t].f+e[t].s-c);
}

bool cycle[mx],cycledone; int cpar[mx],rt;
void dfs2(int c, int p)
{
    for(int t:adj[c]) if(t!=p)
    {
        int k=e[t].f+e[t].s-c; if(cpar[k]==-1) cpar[k]=c, dfs2(k,t); else if(!cycledone)
        {rt=c,cycledone=1; while(1) {cycle[rt]=1; if(rt==k) break; rt=cpar[rt];}}
    }
}
bool vis3[mx]; int cnt3;
void dfs3(int c, int p)
{
    if(vis3[c]) return; vis3[c]=1; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c; if(k==p) continue; dfs3(k,c);
        if(!cycle[k]) cnt3+=k==es[t].f||k==es[t].s;
    }
}
vector<int> cv, cn;
void getcycle(int c)
{
    cn.pb(c); if(c==rt&&!cv.empty()) return; for(int t:adj[c])
    {
        int k=e[t].f+e[t].s-c;
        if(cycle[k]&&!(!cv.empty()&&t==cv.back())) {cv.pb(t), getcycle(k); break;}
    }
}

int solve()
{
#ifdef DEBUG
cout<<"Start\n"<<flush;
#endif
    //note: swap m/n
    int m,n,ans=0; cin>>m>>n;
    for(int i=0; i<n; i++) adj0[i].clear(),adj[i].clear(), vis[i]=vis3[i]=0, cycle[i]=0, cpar[i]=-1;
    for(int i=0; i<m; i++) edge[i]=1;
    //input and delete |T|=1
{
    int a,b;
    for(int i=0; i<m; i++) {int c; cin>>c>>a; if(c==2) cin>>b; else b=0; s1[i]=pi(a-1,b-1);}
    for(int i=0; i<m; i++) {int c; cin>>c>>a; if(c==2) cin>>b; else b=0; s2[i]=pi(a-1,b-1);
        sz1[i]=2-c, adj0[a-1].pb(i); if(c==2) adj0[b-1].pb(i);}
    vector<int> rm; for(int i=0; i<m; i++) if(sz1[i]) rm.pb(i);
    while(!rm.empty())
    {
        int i=rm.back(); rm.pop_back(); if(!edge[i]) continue; if(s2[i].f==-1) return -1;
        ans+=s2[i].f==s1[i].f||s2[i].f==s1[i].s, edge[i]=0;
#ifdef DEBUG
cout<<"Assign "<<i<<' '<<s2[i].f<<" ("<<s2[i].s<<")\n";
#endif
        for(int j:adj0[s2[i].f]) {if(s2[j].f==s2[i].f) s2[j].f=s2[j].s; s2[j].s=-1, rm.pb(j);}
    }
    int E=0;
    for(int i=0; i<m; i++) if(edge[i]) adj[s2[i].f].pb(E),adj[s2[i].s].pb(E), e[E]=s2[i],es[E++]=s1[i];
    m=E;
}
#ifdef DEBUG
cout<<m<<' '<<ans<<'\n'; for(int i=0; i<m; i++) cout<<e[i].f<<' '<<e[i].s<<' '<<es[i].f<<' '<<es[i].s<<'\n';
for(int i=0; i<n; i++) {cout<<i<<'\t'; for(int t:adj[i]) cout<<t<<' '; cout<<'\n';} cout<<flush;
#endif
for(int i=0; i<n; i++) if(!vis[i])
{
    //count edges
    cntE=cntV=0, dfs1(i); if(cntE>2*cntV) return -1;
    if(cntE==2*cntV)
    {
        //cycle with trees: explicit formul
        cycledone=0, dfs2(i,-1);
        cnt3=0, dfs3(rt,-1), ans+=cnt3;
        cv.clear(),cn.clear(), getcycle(rt);
        int A=0,B=0,C=0; for(int j=0; j<cv.size(); j++)
        {
            bool x1=cn[j]==es[cv[j]].f||cn[j]==es[cv[j]].s, x2=cn[j+1]==es[cv[j]].f||cn[j+1]==es[cv[j]].s;
            if(x1&&x2) C++; else if(x1) A++; else if(x2) B++;
        }
        ans+=min(min(A,B)+C,(A+B+C)/2);
    }
    else
    {
        //tree with variable root: dp
        ;
    }
}
    return ans;
}
int main()
{
    int T; cin.sync_with_stdio(0),cin.tie(0),cin>>T; while(T--) cout<<solve()<<'\n';
}
源文件, 语言: C++14

詳細信息 

answer.code:112:5: error: redefinition of ‘int TIMER’
  112 | int TIMER=20;
      |     ^~~~~
answer.code:2:5: note: ‘int TIMER’ previously defined here
    2 | int TIMER=20;
      |     ^~~~~
answer.code:117:32: error: redefinition of ‘const int mx’
  117 | using namespace std; const int mx=1000000; typedef pair<int,int> pi;
      |                                ^~
answer.code:7:32: note: ‘const int mx’ previously defined here
    7 | using namespace std; const int mx=1000000; typedef pair<int,int> pi;
      |                                ^~
answer.code:122:4: error: redefinition of ‘pi s1 [1000000]’
  122 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |    ^~
answer.code:12:4: note: ‘pi s1 [1000000]’ previously defined here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |    ^~
answer.code:122:11: error: redefinition of ‘pi s2 [1000000]’
  122 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |           ^~
answer.code:12:11: note: ‘pi s2 [1000000]’ previously defined here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |           ^~
answer.code:122:24: error: redefinition of ‘bool sz1 [1000000]’
  122 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                        ^~~
answer.code:12:24: note: ‘bool sz1 [1000000]’ previously declared here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                        ^~~
answer.code:122:32: error: redefinition of ‘bool edge [1000000]’
  122 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                                ^~~~
answer.code:12:32: note: ‘bool edge [1000000]’ previously declared here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                                ^~~~
answer.code:122:54: error: redefinition of ‘std::vector<int> adj0 [1000000]’
  122 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                                                      ^~~~
answer.code:12:54: note: ‘std::vector<int> adj0 [1000000]’ previously declared here
   12 | pi s1[mx],s2[mx]; bool sz1[mx],edge[mx]; vector<int> adj0[mx]; //initial sets
      |                                                      ^~~~
answer.code:123:4: error: redefinition of ‘pi e [1000000]’
  123 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |    ^
answer.code:13:4: note: ‘pi e [1000000]’ previously defined here
   13 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |    ^
answer.code:123:10: error: redefinition of ‘pi es [1000000]’
  123 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |          ^~
answer.code:13:10: note: ‘pi es [1000000]’ previously defined here
   13 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |          ^~
answer.code:123:30: error: redefinition of ‘std::vector<int> adj [1000000]’
  123 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |                              ^~~
answer.code:13:30: note: ‘std::vector<int> adj [1000000]’ previously declared here
   13 | pi e[mx],es[mx]; vector<int> adj[mx]; //graph
      |                              ^~~
answer.code:125:5: error: redefinition of ‘int cntE’
  125 | int cntE,cntV; bool vis[mx]; //components
      |     ^~~~
answer.code:15:5: note: ‘int cntE’ previously declared here
   15 | int cntE,cntV; bool vis[mx]; //components
      |     ^~~~
answer.code:125:10: error: redefinition of ‘int cntV’
  125 | int cntE,cntV; bool vis[mx]; //components
      |          ^~~~
answer.code:15:10: note: ‘int cntV’ previously declared here
   15 | int cntE,cntV; bool vis[mx]; //components
      |          ^~~~
answer.code:125:21: error: redefinition of ‘bool vis [1000000]’
  125 | int cntE,cntV; bool vis[mx]; //components
      |                     ^~~
answer.code:15:21: note: ‘bool vis [1000000]’ previously declared here
   15 | int cntE,cntV; bool vis[mx]; //components
      |                     ^~~
answer.code:126:6: error: redefinition of ‘void dfs1(int)’
  126 | void dfs1(int c)
      |      ^~~~
answer.code:16:6: note: ‘void dfs1(int)’ previously defined here
   16 | void dfs1(int c)
      |      ^~~~
answer.code:132:6: error: redefinition of ‘bool cycle [1000000]’
  132 | bool cycle[mx],cycledone; int cpar[mx],rt;
      |      ^~~~~
answer.code:22:6: note: ‘bool cycle [1000000]’ previously declared here
   22 | bool cycle[mx],cycledone; int cpar[mx],rt;
      |      ^~~~~
answer.code:132:16: error: redefinition of ‘bool cycledone’
  132 | bool cycle[mx],cycledone; int cpar[mx],rt;
      |                ^~~~~~~~~
answer.code:22:16: note: ‘bool cycledone’ previously declared here
   22 | bool cycle[mx],cycledone; int cpar[mx],rt;
      |                ^~~~~~~~~
answer.code:132:31: error: redefinition of ‘int cpar [1000000]’
  132 |...
English 繁體中文 简体中文

伺服器時間: 2024-12-03 01:24:39 | 開源專案