oj.uz

Submission #569235

# Submission time Handle Problem Language Result Execution time Memory
569235 2022-05-27T06:00:33 Z Waratpp123 Love Polygon (BOI18_polygon) C++14
29 / 100
 2000 ms 32324 KB 
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
string ss[100010],se[100010];
vector<int> g[100010],gb[100010];
queue<int> topo,bfs;
int in[100010],dp[100010][2],sum,ch[100010],dp2[100010];
void dfs(int i,int p){
    for(auto x : gb[i]){
        if(x==p||in[x]>0) continue;
        dfs(x,i);
    }
    int mx=0;
    for(auto x : gb[i]){
        if(x==p||in[x]>0) continue;
        dp[i][1]+=dp[x][0];
        mx=max(mx,dp[x][1]-dp[x][0]);
    }
    dp[i][0]=mx+dp[i][1];
    dp[i][1]++;
}
int findloop(vector<int> t){
    int mx=0,temp,n=t.size(),i,j;
    if(n==1) return 0;
    if(n==2) {
        mx=max(mx,t[0]);
        mx=max(mx,t[1]);
        mx=max(mx,t[0]+t[1]);
        return mx;
    }
    for(i=0;i<n;i++){
        dp2[i]=max(0,t[i]);
        dp2[(i+1)%n]=max(dp2[i],max(0,t[(i+1)%n]));
        for(j=i+2;j<n+i-1;j++){
            dp2[j%n]=max(dp2[(j+n-1)%n],dp2[(j+n-2)%n]+max(0,t[j%n]));
        }
        mx=max(mx,dp2[(i+n-2)%n]);
    }
    return mx;
}
int main(){
    int n,i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        cin >> ss[i] >> se[i];
        mp[ss[i]]=i;
    }
    if(n%2!=0){
        printf("-1");
        return 0;
    }
    for(i=1;i<=n;i++){
        int sss=mp[ss[i]];
        int sse=mp[se[i]];
        g[sss].push_back(sse);
        gb[sse].push_back(sss);
        in[sse]++;
    }
    for(i=1;i<=n;i++){
        if(in[i]==0) topo.push(i);
    }
    while(!topo.empty()){
        i=topo.front();
        topo.pop();
        in[i]--;
        for(auto x : g[i]){
            in[x]--;
            if(in[x]==0){
                topo.push(x);
            }
        }
    }
    int cnt=0;
    int ans=0;
    for(i=1;i<=n;i++){
        if(in[i]>0){
            dfs(i,-1);
            ans+=dp[i][0];
        }
    }
    vector<int> t;
    for(i=1;i<=n;i++){
        if(in[i]>0){
            if(ch[i]==0){
                bfs.push(i);
                ch[i]=1;
                t.clear();
                while(!bfs.empty()){
                    j=bfs.front();
                    bfs.pop();
                    t.push_back(dp[j][1]-dp[j][0]);
                    for(auto x : g[j]){
                        if(ch[x]==0){
                            bfs.push(x);
                            ch[x]=1;
                        }
                    }
                }
                ans+=(findloop(t));
            }
        }
    }
    printf("%d\n",n-ans);
return 0;
}
/*
8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia
*/

Compilation message

polygon.cpp: In function 'int findloop(std::vector<int>)':
polygon.cpp:23:14: warning: unused variable 'temp' [-Wunused-variable]
   23 |     int mx=0,temp,n=t.size(),i,j;
      |              ^~~~
polygon.cpp: In function 'int main()':
polygon.cpp:73:9: warning: unused variable 'cnt' [-Wunused-variable]
   73 |     int cnt=0;
      |         ^~~
polygon.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~

Subtask #1
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11220 KB Output is correct
2 Correct 5 ms 11220 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 5 ms 11224 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Correct 6 ms 11220 KB Output is correct
8 Incorrect 6 ms 11220 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11220 KB Output is correct
2 Correct 6 ms 11220 KB Output is correct
3 Correct 6 ms 11220 KB Output is correct
4 Execution timed out 2079 ms 28052 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 295 ms 26276 KB Output is correct
2 Correct 292 ms 27444 KB Output is correct
3 Correct 205 ms 26796 KB Output is correct
4 Correct 154 ms 19052 KB Output is correct
5 Correct 300 ms 32324 KB Output is correct
6 Correct 302 ms 25164 KB Output is correct
7 Correct 283 ms 25548 KB Output is correct
8 Correct 234 ms 25772 KB Output is correct
9 Correct 271 ms 24804 KB Output is correct
10 Correct 190 ms 24144 KB Output is correct
11 Correct 6 ms 11220 KB Output is correct
12 Correct 6 ms 11220 KB Output is correct
13 Correct 7 ms 11220 KB Output is correct
14 Correct 7 ms 11220 KB Output is correct

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11220 KB Output is correct
2 Correct 5 ms 11220 KB Output is correct
3 Correct 5 ms 11220 KB Output is correct
4 Correct 5 ms 11224 KB Output is correct
5 Correct 6 ms 11220 KB Output is correct
6 Correct 6 ms 11220 KB Output is correct
7 Correct 6 ms 11220 KB Output is correct
8 Incorrect 6 ms 11220 KB Output isn't correct
9 Halted 0 ms 0 KB -